平衡树（splay）
先以书堆从上到下的下标为权值建立平衡树，对于splay中每个节点记录书的编号
那么现在得到的是有序的书堆
在五个操作之中1,2,3操作较难进行处理
先考虑3操作
当$t=0$时，位置不动，不需要进行操作
当$t=-1$时，可以发现这本书需要插入的位置，就是这个这本书编号对应平衡树中的节点的前驱
那么将前驱的信息与这个节点的信息进行交换即可
同理，当$t=1$时，找出后继，进行交换信息即可
那么考虑1,2操作
对于置顶还是置底，都是将这个节点的权值设为最大或最小
那么记录当前平衡树中权值的最大值和最小值
对于操作的书，先删去其在平衡树中的节点，然后插入权值为最大值+1或最小值-1的节点
并在此节点记录信息即可
#include <bits/stdc++.h> #define inf (int)1e9 using namespace std; const int MAXN=80010; int n,root,t,MAX,MIN; int m; int wh[MAXN]; struct node { int sf,son[2],si,va,fa; int id; }sh[MAXN*4]; int newcode() { ++t; return t; } void pushup(int x) { sh[x].si=1+sh[sh[x].son[0]].si+sh[sh[x].son[1]].si; } void connect(int x,int y,int s) { sh[y].son[s]=x; sh[x].sf=s; sh[x].fa=y; } void clear() { sh[0].fa=sh[0].sf=sh[0].si=sh[0].va=0; memset(sh[0].son,0,sizeof(sh[0].son)); } void rotate(int x) { int sf,fa,y,z,s; s=sh[x].sf; z=sh[x].son[sh[x].sf^1]; sf=sh[sh[x].fa].sf; fa=sh[sh[x].fa].fa; y=sh[x].fa; connect(x,fa,sf); connect(y,x,s^1); connect(z,y,s); clear(); pushup(y); pushup(x); } void splay(int x,int y)//splay基本操作 { while (sh[x].fa!=y) { if (sh[sh[x].fa].fa==y) rotate(x); else if (sh[sh[x].fa].sf==sh[x].sf) { rotate(sh[x].fa); rotate(x); } else { rotate(x); rotate(x); } } if (y==0) root=x; } void insert(int v,int who)//插入 { if (root==0) { sh[newcode()].va=v; sh[t].id=who; wh[who]=t; sh[t].si=1; root=t; return; } int cur; cur=root; while (sh[cur].son[v>sh[cur].va]!=0 && sh[cur].va!=v) cur=sh[cur].son[v>sh[cur].va]; if (v>sh[cur].va) connect(newcode(),cur,1); else connect(newcode(),cur,0); sh[t].va=v; sh[t].id=who; wh[who]=t; sh[t].si=1; pushup(cur); splay(t,0); } void find(int v) { int cur; cur=root; while (sh[cur].son[v>sh[cur].va]!=0 && sh[cur].va!=v) cur=sh[cur].son[v>sh[cur].va]; splay(cur,0); } int per(int v) { find(v); int cur; if (sh[root].va<v) return root; cur=sh[root].son[0]; while (sh[cur].son[1]!=0) cur=sh[cur].son[1]; return cur; } int succ(int v) { find(v); int cur; if (sh[root].va>v) return root; cur=sh[root].son[1]; while (sh[cur].son[0]!=0) cur=sh[cur].son[0]; return cur; } void del(int v) { int p,s; p=per(v); s=succ(v); splay(p,0); splay(s,p); int cur; cur=sh[s].son[0]; sh[s].son[0]=0; sh[cur].fa=0; pushup(cur); pushup(s); pushup(p); } int rk(int x) { find(x); return sh[sh[root].son[0]].si; } int kth(int x,int k) { if (sh[sh[x].son[0]].si<k && k<=sh[sh[x].son[0]].si+1) return x; else if (k<=sh[sh[x].son[0]].si) return kth(sh[x].son[0],k); else return kth(sh[x].son[1],k-1-sh[sh[x].son[0]].si); } int main() { root=0; insert(inf,0); insert(-inf,0); scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { int a; scanf("%d",&a); insert(i,a); } MIN=0; MAX=n+1; while (m--) { char ch[20]; int s; scanf("%s",ch); if (ch[0]=='T') { scanf("%d",&s); del(sh[wh[s]].va); insert(MIN,s); MIN--; } if (ch[0]=='B') { scanf("%d",&s); del(sh[wh[s]].va); insert(MAX,s); MAX++; } if (ch[0]=='I') { int t; scanf("%d%d",&s,&t); if (t==0) continue; int cur,who; if (t==-1) cur=per(sh[wh[s]].va); if (t==1) cur=succ(sh[wh[s]].va); who=sh[cur].id; swap(sh[cur].id,sh[wh[s]].id); swap(wh[who],wh[s]);//交换信息 } if (ch[0]=='A') { scanf("%d",&s); printf("%d ",rk(sh[wh[s]].va)-1);//注意平衡树中还有inf和-inf的节点 } if (ch[0]=='Q') { scanf("%d",&s); printf("%d ",sh[kth(root,s+1)].id); } } }