題目大意：
波妞和加菲貓（這兩個角色也能扯到一起）排隊的時候無聊玩游戲。
把這個隊伍的人從頭到尾標號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(smid)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;
}
