题目大意：

波妞和加菲猫（这两个角色也能扯到一起）排队的时候无聊玩游戏。

把这个队伍的人从头到尾标号1-n

top x操作，把编号为x的人放到对首。

query x操作，x在第几号位置。

rank x操作，x号位置的人的编号是多少。

思路分析：

让你对Splay 的旋转操作的理解更加深刻。

难点在于离散化，

离散出top 和 query 操作中所有的点，因为这些点没有操作队他们进行修改。

所以他们的位置的顺序只收到那些top操作的点的影响。那我们就把这些抽象成一个节点。

比如数据

top 1

top 7

那么我们就有2-6这个区间是不会变的。如果我们执行top 7 之后。

那么把这个区间放到7这个节点的后面就可以了。我们通过size 的计算就可以求的 2-6这几个点的位置了。

我们也离散出了query的操作，是方便到时候query的时候，可以用他的左子树的size+1 就是他的位置了。

然后rank的操作，也是通过size的大小判断。可以通过代码理解。

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #define inf 0x3f3f3f3f #define maxn 122222 #define keyTree (ch[ch[root][1]][0]) using namespace std; typedef long long LL; int S[maxn],que[maxn],ch[maxn][2],pre[maxn],siz[maxn],key[maxn]; int root,top1,top2; int val[maxn],a[maxn],id[maxn]; int high; struct ope { char head; int val; }op[maxn]; struct G//用这个记录离散的区间 或者端点 { int s,e,v; }gap[maxn]; void New(int &x,int PRE,int v) { if(top2)x=S[--top2]; else x=++top1; ch[x][0]=ch[x][1]=0; siz[x]=gap[v].v;//size就是这个区间的大小 pre[x]=PRE; /*special*/ val[x]=gap[v].v; id[v]=x;//第v个区间对应的是节点是第几个 key[x]=v;//x号节点是哪个区间 //好纠结。。。 } void pushup(int x)/*special*/ { siz[x]=siz[ch[x][0]]+siz[ch[x][1]]+val[x]; } void build(int &x,int s,int e,int f) { if(s>e)return; int mid=(s+e)>>1; New(x,f,mid); if(s
      
       mid)build(ch[x][1],mid+1,e,x); pushup(x); } void Rotate(int x,int kind) { int y=pre[x]; ch[y][!kind]=ch[x][kind]; pre[ch[x][kind]]=y; if(pre[y])ch[pre[y]][ch[pre[y]][1]==y]=x; pre[x]=pre[y]; ch[x][kind]=y; pre[y]=x; pushup(y); } void Splay(int x,int goal) { while(pre[x]!=goal) { if(pre[pre[x]]==goal) Rotate(x,ch[pre[x]][0]==x); else { int y=pre[x]; int kind=ch[pre[y]][0]==y; if(ch[y][kind]==x){ Rotate(x,!kind); Rotate(x,kind); } else { Rotate(y,kind); Rotate(x,kind); } } } pushup(x); if(goal==0)root=x; } void erase(int x) { int y=pre[x]; int head=0,tail=0; for(que[tail++]=x;head
       
        >1; if(gap[mid].s<=key_val)low=mid+1; else hig=mid-1; } return low-1; } void remove() {//删除根节点 int tmp; int r=ch[root][0]; if(r==0) { tmp=root; root=ch[root][1]; pre[root]=0; pushup(root); ch[tmp][0]=ch[tmp][1]=0; erase(tmp); return ; } else { while(ch[r][1])r=ch[r][1]; Splay(r,root); int tmp=root; ch[r][1]=ch[root][1]; pre[ch[root][1]]=r; pre[r]=0; root=r; pushup(root); ch[tmp][0]=ch[tmp][1]=0; erase(tmp); } } void Top(int x) {//top操作 int k=bin(x); int y=id[k]; Splay(y,0); int tmp=y; remove(); insert(root,k,0); Splay(y,0); } int query(int x) { int k=bin(x);//先找到x对应在哪个区间 int y=id[k];//这个区间在Splay上第几号节点 Splay(y,0); return siz[ch[root][0]]+1; } int rank(int r,int k) { int t=siz[ch[r][0]]; if(k<=t) return rank(ch[r][0],k); else if(k<=t+val[r]) return gap[key[r]].s+(k-t)-1; else return rank(ch[r][1],k-t-val[r]); } void init(int n)/*special*/ { root=top1=top2=0; ch[0][0]=ch[0][1]=siz[0]=pre[0]=0; build(root,1,n,0); } int main() { int T; scanf("%d",&T); for(int CASE=1;CASE<=T;CASE++) { int n,m; scanf("%d%d",&n,&m); int top=0; for(int i=1;i<=m;i++) { char str[10]; scanf("%s%d",str,&op[i].val); op[i].head=str[0]; if(str[0]=='T'||str[0]=='Q') { a[++top]=op[i].val; } } a[++top]=n;//这个地方啊啊啊啊 sort(a+1,a+1+top); high=unique(a+1,a+1+top)-a-1; int cnt=1; a[0]=0;//还有这个地方啊啊啊 for(int i=1;i<=high;i++) { if(a[i]-a[i-1]>1){//中间的区间 gap[cnt].s=a[i-1]+1; gap[cnt].e=a[i]-1; gap[cnt].v=gap[cnt].e-gap[cnt].s+1; cnt++; }//端点 gap[cnt].s=a[i]; gap[cnt].e=a[i]; gap[cnt].v=gap[cnt].e-gap[cnt].s+1; cnt++; } high=cnt-1; init(high); printf("Case %d:\n",CASE); for(int i=1;i<=m;i++) { if(op[i].head=='T') Top(op[i].val); else if(op[i].head=='Q') printf("%d\n",query(op[i].val)); else printf("%d\n",rank(root,op[i].val)); } } return 0; }