edward_mj

【题目大意】

一开始给定n个人，他们按编号1..n地排好了。

有3个操作。

分别是：

Top x：把编号为x个人放到a[1]。然后a[1..x-1]的数都向后移一位。

Query x：返回编号为x个人现在在哪里位置。

Rank x：返回排名在x的这个人是编号是多少？

【算法分析】

我采用的是Splay来离线解决。

由于n高达10^8。所以不能完全模拟。

首先是把询问都读进来，然后对于Top和Query碰到的编号，开一个List取出来，排序并去重。

然后开始构建Splay。

对于在List中的编号，我们把他构建成一个结点。

然后对于List[i]和List[i-1]之间的间隙结点，我把它们都压缩成一个结点。（当然Size的计算方法就有点不同了。）

然后这样，Splay上最多有2*Q个点了。

对于Top操作，我们就相当于删掉这个点，再插入一次这个点。

对于Query，我们可以直接把这个点Splay到根，然后算他的左子树的Size，+1就是答案。

对于Rank，我们就像找第k个元素那样，找到那个对应位置，输出就行了。（就是压缩块有点不同而已）

【其它】

2TLE。写惯了SBT。。。那个父亲的域老是忘了维护，导致死循环了。

【CODE】

#include

#include

#include #define update(p) (Tr[p].Size=Tr[ch[p][0]].Size+Tr[ch[p][1]].Size+Tr[p].weight)
const int N=305555;

struct Splay_t{
       int root,tot,Lasttop;
       int ch[N][2],pre[N];
       struct Node{int St,Size,weight;}Tr[N];
      
       void init(){
            root=tot=1;
            Lasttop=2;
            ch[1][0]=ch[1][1]=0;
            Tr[0].Size=0;
            pre[1]=0;
       }
      
       void rotate(int x,int T){
            int y=pre[x];
            if (T){
              ch[y][0]=ch[x][1];
              ch[x][1]=y;
              pre[ch[y][0]]=y;
              pre[x]=pre[y];
              pre[y]=x;
            }
            else{
              ch[y][1]=ch[x][0];
              ch[x][0]=y;
              pre[ch[y][1]]=y;
              pre[x]=pre[y];
              pre[y]=x;
            }
            if (ch[pre[x]][0]==y) ch[pre[x]][0]=x;
                             else ch[pre[x]][1]=x;
            update(y);
            update(x);
       }
      
       void Splay(int x,int cut){
            if (x==cut) return;
            int y,z;
            while (pre[x]!=cut){
                  y=pre[x]; z=pre[y];
                  if (z==cut) rotate(x,ch[y][0]==x);
                  else
                  if (ch[z][0]==y)
                    if (ch[y][0]==x) {rotate(y,1); rotate(x,1);}
                                else {rotate(x,0); rotate(x,1);}
                  else
                    if (ch[y][1]==x) {rotate(y,0); rotate(x,0);}
                                else {rotate(x,1); rotate(x,0);}
            }
       }
      
       void Ins(int St,int weight){
            tot++;
            ch[tot][0]=ch[tot][1]=0;
            Tr[tot].St=St;
            Tr[tot].weight=Tr[tot].Size=weight;
            if (tot==2){
              ch[root][0]=2;
              pre[2]=root;
            }
            else{
              Splay(tot-1,root);
              ch[tot-1][1]=tot;
              update(tot-1);
              pre[tot]=tot-1;
            }
            Splay(tot,root);
       }
      
       void Top(int x){
            if (Lasttop==x) return;
            Splay(x,root);
            int p,q;
            q=x; p=ch[x][1];
            while (p){
                  q=p;
                  p=ch[p][0];
            }
            if (q==x){
              ch[1][0]=ch[x][0];
              pre[ch[x][0]]=1;
            }
            else{
              Splay(q,x);
              ch[q][0]=ch[x][0];
              pre[q]=1;
              pre[ch[x][0]]=q;
              ch[1][0]=q;
              update(q);
            }
            Splay(Lasttop,root);
            ch[Lasttop][0]=x;
            pre[x]=Lasttop;
            ch[x][0]=ch[x][1]=0;
            update(x);
            update(Lasttop);
            Lasttop=x;
       }      
      
       int Query(int x){
           Splay(x,root);
           return Tr[ch[x][0]].Size+1;
       }
      
       int rank(int x){
           int p,done=0;
           p=ch[root][0];
           while (1){
                 if (x<=Tr[ch[p][0]].Size+done)
                   p=ch[p][0];
                 else
                 if (x>Tr[ch[p][0]].Size+done+Tr[p].weight){
                   done+=Tr[ch[p][0]].Size+Tr[p].weight;
                   p=ch[p][1];
                 }
                 else break;
           }
           Splay(p,root);
           return x-Tr[ch[p][0]].Size+Tr[p].St-1;
       }
      
}Splay;
int n,Q,Lt;
int op[N],a[N],List[N],pos[N];

int cmp(const void *A,const void *B){return *((int*)A) – *((int*)B);}
void init(){
     int i,cnt;
     Lt=List[0]=0;
     char Str[100];
     scanf("%d%d",&n,&Q);
     for (i=1;i<=Q;i++){
         scanf("%s%d",Str,&a[i]);
         switch (Str[0]){
                case ‘T’:op[i]=1; break;
                case ‘Q’:op[i]=2; break;
                case ‘R’:op[i]=3; break;
         }
         if (op[i]!=3) List[++Lt]=a[i];
     }
     qsort(List+1,Lt,sizeof(int),cmp);
     for (i=1,cnt=0;i<=Lt;i++){
         cnt+=(!cnt || List[i]!=List[cnt]);
         List[cnt]=List[i];
     }
     Lt=cnt;
}

void pre_Insert(){
     int i;
     Splay.init();
     for (List[0]=0,i=1;i<=Lt;i++){
         if (List[i]-List[i-1]>1)
           Splay.Ins(List[i-1]+1,List[i]-List[i-1]-1);
         Splay.Ins(List[i],1);
         pos[i]=Splay.tot;
     }
}

int Find(int x){
    int l=1,r=Lt,mid;
    while (l          mid=(l+r)/2;
          if (x>List[mid]) l=mid+1;
                      else r=mid;
    }
    return pos[l];
}

void solve(){
     int i;
     for (i=1;i<=Q;i++)
       switch (op[i]){
              case 1:Splay.Top(Find(a[i])); break;
              case 2:printf("%dn",Splay.Query(Find(a[i]))); break;
              case 3:
                   if (a[i]>List[Lt]) printf("%dn",a[i]);
                                 else printf("%dn",Splay.rank(a[i]));
                   break;
       }
}

int main(){
    int Tc,i;
    scanf("%d",&Tc);
    for (i=1;i<=Tc;i++){
        printf("Case %d:n",i);
        init();
        pre_Insert();
        solve();
    }
}