1861: [Zjoi2006]Book 书架
Time Limit: 4 Sec Memory Limit: 64 MB
Submit: 1453 Solved: 822
[Submit][Status][Discuss]
Description
小T有一个很大的书柜。这个书柜的构造有些独特，即书柜里的书是从上至下堆放成一列。她用1到n的正整数给每本书都编了号。 小T在看书的时候，每次取出一本书，看完后放回书柜然后再拿下一本。由于这些书太有吸引力了，所以她看完后常常会忘记原来是放在书柜的什么位置。不过小T的记忆力是非常好的，所以每次放书的时候至少能够将那本书放在拿出来时的位置附近，比如说她拿的时候这本书上面有X本书，那么放回去时这本书上面就只可能有X-1、X或X+1本书。 当然也有特殊情况，比如在看书的时候突然电话响了或者有朋友来访。这时候粗心的小T会随手把书放在书柜里所有书的最上面或者最下面，然后转身离开。 久而久之，小T的书柜里的书的顺序就会越来越乱，找到特定的编号的书就变得越来越困难。于是她想请你帮她编写一个图书管理程序，处理她看书时的一些操作，以及回答她的两个提问：(1)编号为X的书在书柜的什么位置；(2)从上到下第i本书的编号是多少。
Input
第一行有两个数n，m，分别表示书的个数以及命令的条数；第二行为n个正整数：第i个数表示初始时从上至下第i个位置放置的书的编号；第三行到m+2行，每行一条命令。命令有5种形式： 1． Top S——表示把编号为S的书房在最上面。 2． Bottom S——表示把编号为S的书房在最下面。 3． Insert S T——T∈{-1，0，1}，若编号为S的书上面有X本书，则这条命令表示把这本书放回去后它的上面有X+T本书； 4． Ask S——询问编号为S的书的上面目前有多少本书。 5． Query S——询问从上面数起的第S本书的编号。
Output
对于每一条Ask或Query语句你应该输出一行，一个数，代表询问的答案。
Sample Input
1 3 2 7 5 8 10 4 9 6
Query 3
Top 5
Ask 6
Bottom 3
Ask 3
Top 6
Insert 4 -1
Query 5
Query 2
Ask 2
Sample Output
9
9
7
5
3
HINT
数据范围
Source
————————————————————————
splay维护序列的裸题
只需要维护一个子树大小size
1.top 将一个点删除，插入到根节点最左儿子
2.bottom 将一个点删除，插入到根节点最右儿子
3.insert +1 -1 （记录s前一个点为prev，后一个点为next）
-1 prev提根，s插在prev和它的左儿子之间
+1 next提根，s插在next和它的右儿子之间
4.ask s提根，左儿子的size
5.query 递归查找即可
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <string.h>
#define siji(i,x,y) for(int i=(x);i<=(y);++i)
#define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
#define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
#define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
#define inf 0x1f1f1f1f
#define ivorysi
#define mo 97797977
#define hash 974711
#define base 47
#define MAXN 100005
#define fi first
#define se second
#define pii pair<int,int>
using namespace std;
typedef long long ll;
struct node {
int size,son[],fa;
void clear() {
size=son[]=son[]=fa=;
}
}tree[MAXN];
int root;
//维护size
void update(int x,int c) {
int k=tree[x].size;
int o=tree[x].fa;
tree[x].size=tree[o].size;
tree[o].size=tree[o].size-k+tree[tree[x].son[c]].size;
}
void rotate(int x,int c) {
update(x,c);
int o=tree[x].fa;
if(tree[o].fa!=) {
int t= o==tree[tree[o].fa].son[] ? : ;
tree[tree[o].fa].son[t]=x;
}
tree[o].son[c^]=tree[x].son[c];
if(tree[o].son[c^])tree[tree[o].son[c^]].fa=o;
tree[x].son[c]=o;
tree[x].fa=tree[o].fa;
tree[o].fa=x; }
void splay(int x,int y) {
while(tree[x].fa!=y) {
int k1= x==tree[tree[x].fa].son[] ? : ;
int k2= tree[x].fa == tree[tree[tree[x].fa].fa].son[] ? : ;
if(tree[tree[x].fa].fa!=y && k2==k1) {
rotate(tree[x].fa,k1);
rotate(x,k1);
}
else {
rotate(x,k1);
}
}
if(y==) root=x;
else { }
}
int find(int x,int c) {
splay(x,);
int t=tree[x].son[c];
while(tree[t].son[c^]!=) {
t=tree[t].son[c^];
}
return t;
}
void delete_x(int prev,int next) {
if(prev!= && next!=) {
splay(prev,);
splay(next,prev);
tree[tree[root].son[]].son[]=;
--tree[tree[root].son[]].size;
}
else if(prev!=) {
splay(prev,);
tree[root].son[]=;
}
else {
splay(next,);
tree[root].son[]=;
}
--tree[root].size;
}
//0是top 1是bottom
void in_hurry(int x,int c) {
int pr=find(x,),ne=find(x,);
delete_x(pr,ne);
int t=root;
++tree[t].size;
tree[x].son[c^]=tree[t].son[c];
tree[tree[t].son[c]].fa=x;
tree[x].size=tree[tree[t].son[c]].size+;
tree[x].fa=t;
tree[t].son[c]=x;
}
int ask(int x) {
splay(x,);
return tree[tree[x].son[]].size;
}
void insert(int x,int c) {
if(c==) return;
if(ask(x)== && c==-) return;
int pr=find(x,),ne=find(x,);
delete_x(pr,ne);
int t= c==- ? pr : ne;
splay(t,);
c= c==- ? : ;
++tree[t].size;
tree[x].clear();
tree[x].son[c]=tree[t].son[c];
tree[tree[t].son[c]].fa=x;
tree[x].size=tree[tree[t].son[c]].size+;
tree[t].son[c]=x;
tree[x].fa=t;
splay(x,);
} void query(int x,int s) {
int temp=tree[tree[x].son[]].size+;
if(s==temp) {splay(x,);return;}
int t=s<temp ? : ;
s = s>=temp ? s-temp : s;
query(tree[x].son[t],s);
}
int n,m;
void init() {
scanf("%d%d",&n,&m);
int a=,b;
siji(i,,n) {
scanf("%d",&b);
tree[b].fa=a;
if(a!=) {
tree[a].son[]=b;
}
else {root=b;}
tree[b].size=n-i+;
a=b;
} }
void solve() {
init();
char ord[];
int s,t;
siji(i,,m) {
scanf("%s",ord);
if(ord[]=='T' || ord[]=='B' ) {
t=ord[]=='T' ? : ;
scanf("%d",&s);
in_hurry(s,t);
}
else if(ord[]=='I') {
scanf("%d%d",&s,&t);
insert(s,t);
}
else if(ord[]=='A'){
scanf("%d",&s);
printf("%d\n",ask(s));
}
else if(ord[]=='Q') {
scanf("%d",&s);
query(root,s);
printf("%d\n",root);
}
}
}
int main(int argc, char const *argv[])
{
#ifdef ivorysi
freopen("f1.in","r",stdin);
#endif
solve();
}