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
10 10
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
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
2
9
9
7
5
3
9
9
7
5
3
HINT
数据范围
100%的数据，n,m < = 80000
Solution
这个题还是很裸的，只不过我犯了一个非常sb的错误然后调了好久emm……
操作原理在函数中
操作原理在函数中
Code
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N (100000+100)
using namespace std;
int Size[N],Key[N];//key存编号
int Father[N],Son[N][];
int n,m,Root,a[N],x,t;
int point[N];//存编号i对应的是splay的哪个点
char s[N]; int Get(int x){return Son[Father[x]][]==x;}
void Update(int x){Size[x]=Size[Son[x][]]+Size[Son[x][]]+;}
void Clear(int x){Father[x]=Son[x][]=Son[x][]=Size[x]=;}
int Pre(){int now=Son[Root][]; while (Son[now][]) now=Son[now][];return now;}
int Next(){ int now=Son[Root][];while (Son[now][]) now=Son[now][];return now;} void Build(int l,int r,int fa)
{
if (l>r) return;
if (l==r)
{
Size[l]=;
Key[l]=a[l];
Father[l]=fa;
Son[fa][l>fa]=l;
return;
}
int mid=(l+r)/;
Build(l,mid-,mid);
Build(mid+,r,mid);
Father[mid]=fa;
Son[fa][mid>fa]=mid;
Key[mid]=a[mid];
Update(mid);
} void Rotate(int x)
{
int wh=Get(x);
int fa=Father[x],fafa=Father[fa];
Son[fa][wh]=Son[x][wh^];
Father[fa]=x;
if (Son[fa][wh]) Father[Son[fa][wh]]=fa;
Son[x][wh^]=fa;
Father[x]=fafa;
if (fafa) Son[fafa][Son[fafa][]==fa]=x;
Update(fa);
Update(x);
} void Splay(int x)
{
for (int fa; fa=Father[x]; Rotate(x))
if (Father[fa])
Rotate(Get(fa)==Get(x)?fa:x);
Root=x;
} int Findx(int x)
{
int now=Root;
while ()
if (x<=Size[Son[now][]])
now=Son[now][];
else
{
x-=Size[Son[now][]];
if (x==)
{
Splay(now);
return Key[now];
}
x--;
now=Son[now][];
}
} void Delete(int x)
{
Findx(x);
if (!Son[Root][] && !Son[Root][])
{
Clear(Root);
Root=;
return;
}
if (!Son[Root][])
{
Root=Son[Root][];
Clear(Father[Root]);
Father[Root]=;
return;
}
if (!Son[Root][])
{
Root=Son[Root][];
Clear(Father[Root]);
Father[Root]=;
return;
}
Splay(x);
int pre=Pre(),old=x;
Splay(pre);
Son[Root][]=Son[old][];
Father[Son[old][]]=Root;
Clear(old);
Update(Root);
} void Top(int x)//就是将一个点删除掉然后放到哨兵节点1的右儿子上。若右儿子有点就把原来的右儿子当做插入节点的右儿子
{
Delete(x);
int now=Root;
while (Son[now][]) now=Son[now][];
int old=Son[now][];
Father[x]=now;
Son[now][]=x;
Father[old]=x;
Son[x][]=old;
Update(x);
Splay(x);
} void Bottom(int x)//同上
{
Delete(x);
int now=Root;
while (Son[now][]) now=Son[now][];
int old=Son[now][];
Father[x]=now;
Son[now][]=x;
Father[old]=x;
Son[x][]=old;
Update(now);
Splay(x);
} void Ins(int x,int t)//-1(+1同理)：先把x删掉，再把x前驱splay到根，再把x插到根的前驱位置的叶子
{
int y,z;
if (t==-)
{
Splay(x);
y=Pre();
Delete(x);
Splay(y);
z=Pre();
Father[x]=z;
Son[z][]=x;
Size[x]=;
Update(z);
Splay(x);
}
if (t==)
{
Splay(x);
y=Next();
Delete(x);
Splay(y);
z=Next();
Father[x]=z;
Son[z][]=x;
Size[x]=;
Update(z);
Splay(x);
} } int Ask(int x)//emmm……
{
Splay(x);
return Size[Son[x][]]-;
} int main()
{
scanf("%d%d",&n,&m);
for (int i=; i<=n; ++i)
{
scanf("%d",&a[i+]);
point[a[i+]]=i+;
}
Build(,n+,);
Root=(n+)/;
for (int i=; i<=m; ++i)
{
scanf("%s%d",&s,&x);
if (s[]=='T') Top(point[x]);
if (s[]=='B') Bottom(point[x]);
if (s[]=='I') scanf("%d",&t),Ins(point[x],t);
if (s[]=='A') printf("%d\n",Ask(point[x]));
if (s[]=='Q') printf("%d\n",Findx(x+));
}
}