题意：
Ponyo and Garfield are waiting outside the box-office for theirfavorite movie. Because queuing is so boring, that they want to play a game tokill the time. The game is called “Queue-jumpers”. Suppose that there are Npeople numbered from 1 to N stand in a line initially. Each time you should simulateone of the following operations:
1. Top x:Take person x to the front of the queue
2. Queryx: calculate the current position of person x
3. Rankx: calculate the current person at position x
Where x is in [1,N].
Ponyo is so cleverthat she plays the game very well while Garfield has no idea. Garfield is nowturning to you for help.
题解：
伸展树的应用：
对于操作1：现将x旋转到根节点，删除根，用右边最小的节点当根，然后把右边最小的旋转到根，此时根左边已经没有节点。然后将x节点作为根节点，右节点指向刚才那个根，左节点为0，即完成插入首部。
对于操作2：找排名。
对于操作3：左右找呗！
N过大，对TOP命令进行区间离散化。
#include<bits/stdc++.h>using namespace std;const int maxn = 2e5+99;int n,q,t;
int s[maxn],e[maxn],cnt;int p[maxn];
char op[maxn][10];
int qnum[maxn];int bin(int x)
{int l=1-1,r=cnt+1;while(r>l+1){int m = (l+r)>>1;if(s[m] <= x && x<= e[m])return m;else if(x<s[m])r=m;else l = m;}return -1;
}int sz[maxn],num[maxn],pre[maxn],ch[maxn][2],root;void pushup(int r)
{sz[r] = sz[ch[r][0]]+sz[ch[r][1]]+num[r];
}void rotate(int x,int d)
{int y = pre[x];ch[y][!d] = ch[x][d];pre[ch[x][d]] = y;if(pre[y])ch[pre[y]][ch[pre[y]][1]==y] = x;pre[x] = pre[y];ch[x][d] = y;pre[y] = x;pushup(y);
}void splay(int r,int goal)
{while(pre[r]!=goal){if(pre[pre[r]]==goal)rotate(r,ch[pre[r]][0]==r);else{int y = pre[r];int d = ch[pre[y]][0] == y;if(ch[y][d] == r){rotate(r,!d);rotate(r,d);}else{rotate(y,d);rotate(r,d);}}}pushup(r);if(goal==0)root = r;
}void newnode(int &r,int fa,int k)
{r = k;num[r] = sz[r] = e[k] - s[k] + 1;pre[r] = fa;ch[r][0] = ch[r][1] = 0;
}void build(int &x,int l,int r,int fa)
{if(l>r)return;int m = (l+r)>>1;newnode(x,fa,m);build(ch[x][0],l,m-1,x);build(ch[x][1],m+1,r,x);pushup(x);
}void init()
{root = 0;pre[root] = ch[root][0] = ch[root][1] = sz[root] = num[root] = 0;build(root,1,cnt,0);
}int getmin(int r)
{while(ch[r][0]){r = ch[r][0];}return r;
}void ddelete()
{if(ch[root][0]==0 || ch[root][1]==0){root = ch[root][0] + ch[root][1];pre[root] = 0;return;}int k = getmin(ch[root][1]);splay(k,root);ch[k][0] = ch[root][0];pre[ch[root][0]]=k;root = k;pre[k] = 0;pushup(root);//不用加也可
}void top(int x)
{int r = bin(x);splay(r,0);ddelete();splay(getmin(root),0);ch[r][0] = 0;ch[r][1] = root;pre[r] = 0;pre[root] = r;root = r;pushup(r);
}int query(int x)
{int r = bin(x);splay(r,0);return sz[ch[r][0]]+x-s[r]+1;
}int getrank(int r,int k)
{int t = sz[ch[r][0]];if(k<=t)return getrank(ch[r][0],k);else if(k<=t+num[r])return s[r]+k-t-1;else return getrank(ch[r][1],k-t-num[r]);
}int main()
{scanf("%d",&t);for(int kase = 1;kase<=t;kase++){scanf("%d%d",&n,&q);int t = 0;for(int i=1;i<=q;i++){scanf("%s%d",op[i],qnum+i);if(op[i][0] == 'T'){p[t++] = qnum[i];}}p[t++] = 1;p[t++] = n;sort(p,p+t);t = unique(p,p+t)-p;cnt = 0;for(int i = 0;i<t;i++){if(i>0 && p[i]>p[i-1]+1){cnt++;s[cnt] = p[i-1]+1;e[cnt] = p[i] - 1;}cnt++;s[cnt] = e[cnt] = p[i];}init();printf("Case %d:\n",kase);for(int i=1;i<=q;i++){if(op[i][0] == 'T')top(qnum[i]);else if(op[i][0]=='Q')printf("%d\n",query(qnum[i]) );else if(op[i][0]=='R')printf("%d\n",getrank(root,qnum[i]));}}
}