题意：

n个人站成一排  一开始是从1到n有序的  现在有三个操作  Top操作是将一个人排到队首  Query操作是询问某个人现在排第几  Rank操作是询问排某个位置的人是谁

思路：

将队伍扭来扭去…  很像splay的旋转吧（哪像了！！）

这是个不错的splay题…

首先  n很大  但是操作不多  想到离散化

离散化还有个技巧  我们发现只有top和query操作对单人进行  rank和人没什么关系

所以要把top和query操作的人单独拿出来  那么其他的人就可以用区间的形式来表示了

我们只需要开一个num数字来表示树上这个点（表示一个区间）包含几个人

然后就是对每个操作的处理  从简到难

Rank操作最简单  它根本和人没关系  只要找第k个位置就好了  不过我们现在的点表示的是一个区间

那也不难处理  开一个sum数组对num进行维护  就可以简单的找到第k个人所在区间  算一下他是谁就好

接着是Query操作  这个有点烦  因为我们不知道包含k这个人的区间是哪个

其实好解决  开个idx数字记录树上的点表示第几个区间  再开一个qu数组表示某个区间对应树上的点就好

找到了点然后呢？  把它转到根  然后sum[L(root)]+1就是答案！！

最后是Top  有了query的铺垫那么我们只要找到这个点  把它转到根  再把它的前驱转到根下面

删除根节点  再把删掉的这个点插到队首  一个top操作就完成了

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
#define keytree ch[ch[root][1]][0]
#define L(x) ch[x][0]
#define R(x) ch[x][1]
#define N 201000

int T,t,n,m,tot,root;
int ch[N][2],pre[N],size[N],num[N],sum[N],idx[N],qu[N],a[N],s[N],e[N],op[N],opn[N];

void newnode(int &u,int fa,int w)
{
    u=++tot;
    L(u)=R(u)=0;
    pre[u]=fa;
    size[u]=1;
    if(w)
    {
        sum[u]=num[u]=e[w]-s[w]+1;
        idx[w]=u;
        qu[u]=w;
    }
}

void up(int u)
{
    size[u]=size[L(u)]+size[R(u)]+1;
    sum[u]=num[u]+sum[L(u)]+sum[R(u)];
}

void down(int u)
{
}

void rotate(int u,int kind)
{
    int fa=pre[u];
    down(fa);
    down(u);
    ch[fa][!kind]=ch[u][kind];
    pre[ch[u][kind]]=fa;
    if(pre[fa]) ch[pre[fa]][ch[pre[fa]][1]==fa]=u;
    pre[u]=pre[fa];
    ch[u][kind]=fa;
    pre[fa]=u;
    up(fa);
}

void splay(int u,int goal)
{
    int fa,kind;
    down(u);
    while(pre[u]!=goal)
    {
        if(pre[pre[u]]==goal) rotate(u,L(pre[u])==u);
        else
        {
            fa=pre[u];
            kind=L(pre[fa])==fa;
            if(ch[fa][kind]==u)
            {
                rotate(u,!kind);
                rotate(u,kind);
            }
            else
            {
                rotate(fa,kind);
                rotate(u,kind);
            }
        }
    }
    up(u);
    if(goal==0) root=u;
}

int getkth(int u,int k)
{
    down(u);
    int tmp=size[L(u)]+1;
    if(tmp==k) return u;
    if(tmp>k) return getkth(L(u),k);
    else return getkth(R(u),k-tmp);
}

int getkperson(int u,int k)
{
    down(u);
    int tmp=sum[L(u)];
    if(k>tmp&&k<=tmp+num[u]) return s[qu[u]]+k-tmp-1;
    if(tmp>=k) return getkperson(L(u),k);
    else return getkperson(R(u),k-tmp-num[u]);
}

void build(int &u,int l,int r,int fa)
{
    if(l>r) return ;
    int mid=(l+r)>>1;
    newnode(u,fa,mid);
    build(L(u),l,mid-1,u);
    build(R(u),mid+1,r,u);
    up(u);
}

void init()
{
    root=tot=0;
    L(root)=R(root)=pre[root]=size[root]=num[root]=sum[root]=idx[root]=0;
    newnode(root,0,0);
    newnode(R(root),root,0);
    build(keytree,1,n,R(root));
    up(R(root));
    up(root);
}

int getpre(int u)
{
    down(u);
    u=L(u);
    down(u);
    while(R(u))
    {
        u=R(u);
        down(u);
    }
    return u;
}

void remove()
{
    if(L(root))
    {
        int i=getpre(root);
        splay(i,root);
        R(i)=R(root);
        pre[R(root)]=i;
        root=L(root);
        pre[root]=0;
        up(root);
    }
    else
    {
        root=R(root);
        pre[root]=0;
    }
}

void insert(int u)
{
    keytree=u;
    pre[u]=R(root);
    L(u)=R(u)=0;
    up(u);
    up(pre[u]);
    up(root);
}

int main()
{
    //freopen("test.in","r",stdin);
    //freopen("test.out","w",stdout);
    int i,j,k;
    char str[3];
    while(~scanf("%d",&T))
    {
        for(t=1;t<=T;t++)
        {
            printf("Case %d:\n",t);
            scanf("%d%d",&n,&m);
            for(i=j=1;i<=m;i++)
            {
                scanf("%s%d",str,&opn[i]);
                if(str[0]=='T')
                {
                    op[i]=1;
                    a[j++]=opn[i];
                }
                else if(str[0]=='Q')
                {
                    op[i]=2;
                    a[j++]=opn[i];
                }
                else op[i]=3;
            }
            sort(a+1,a+j);
            a[0]=0;
            for(i=k=1;i<j;i++)
            {
                if(a[i]!=a[i-1])
                {
                    if(a[i]-a[i-1]>1)
                    {
                        s[k]=a[i-1]+1;
                        e[k]=a[i]-1;
                        k++;
                    }
                    s[k]=a[i];
                    e[k]=a[i];
                    k++;
                }
            }
            if(a[j-1]!=n)
            {
                s[k]=a[j-1]+1;
                e[k]=n;
            }
            else k--;
            n=k;
            init();
            for(i=1;i<=m;i++)
            {
                if(op[i]==1)
                {
                    k=lower_bound(s+1,s+n+1,opn[i])-s;
                    k=idx[k];
                    splay(k,0);
                    remove();
                    splay(getkth(root,1),0);
                    splay(getkth(root,2),root);
                    insert(k);
                }
                else if(op[i]==2)
                {
                    k=lower_bound(s+1,s+n+1,opn[i])-s;
                    k=idx[k];
                    splay(k,0);
                    printf("%d\n",sum[L(root)]+1);
                }
                else if(op[i]==3)
                {
                    k=getkperson(root,opn[i]);
                    printf("%d\n",k);
                }
            }
        }
    }
    return 0;
}

HDU 3436 Queue-jumpers