hdu-3436 Queue-jumpers（伸展樹）

題目連結

伸展樹講解

題意：一串數字，有三種操作：

Top x 将x移至數列首；

Query x 詢問x的位置；

Rank x 詢問位置x的數。

思路：伸展樹。top操作需要先删除再插入；rank操作根據size和節點代表的區間長度（len）二分查找；query操作先将x旋轉至根，然後根據size+1便為答案。

需要注意的是，資料範圍大，需離散化，是以對于top和query詢問的點單獨出來，其他區間縮點存入樹中。

一題敲了一天也算有點了解了。

//#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <map>
#include <algorithm>
#include <conio.h>
#include <iostream>
using namespace std;
#define rd(x) scanf("%d",&x)
#define rd2(x,y) scanf("%d%d",&x,&y)
#define maxn 100005
#define pii pair<int,int>
struct node{
    node *ch[2],*fa;//son father
    int sz,v,len;
    node(){ch[0]=ch[1]=fa=NULL;}
};
node *root;
void push_up(node *x){//更新size
    x->sz=x->len;
    if(x->ch[0]) x->sz+=x->ch[0]->sz;
    if(x->ch[1]) x->sz+=x->ch[1]->sz;
}
void rotat(node *x){
    node *f=x->fa,*ff=x->fa->fa;
    int c=f->ch[1]==x?1:0;
    if(x->ch[!c]) x->ch[!c]->fa=f;//x的兒子變為fa的兒子
    f->ch[c]=x->ch[!c];
    x->fa=ff;//兒子的父親變為父親的父親
    if(ff) {
        int cc=ff->ch[1]==f?1:0;
        ff->ch[cc]=x;
    }
    x->ch[!c]=f;//x變為fa的父親
    f->fa=x;
    push_up(f);
    push_up(x);
}
void splay(node* x,node *goal){//将x轉到goal的兒子位置
    node *f,*ff;
    int c,cc;
    while(x->fa!=goal){
        if(x->fa->fa==goal) rotat(x);
        else{
            f=x->fa;ff=x->fa->fa;
            c=x==f->ch[1]?1:0;
            cc=f==ff->ch[1]?1:0;
            c==cc?rotat(f):rotat(x);
            rotat(x);
        }
    }
    if(goal==NULL) root=x;
    push_up(x);
}
void Insert(node *x){//插入到隊首
    if(root==NULL) {
        root=x;
        x->ch[0]=x->ch[1]=x->fa=NULL;
        push_up(x);
        return;
    }
    node *p=root;
    while(p->ch[0]) p=p->ch[0];
    p->ch[0]=x;x->fa=p;
    x->ch[0]=x->ch[1]=NULL;
    splay(x,NULL);
}
void Erase(node *x){//删除再插入
    splay(x,NULL);
    if(x->ch[0]==NULL) {
            return;
    }
    if(x->ch[1]==NULL) {
            root=x->ch[0];
    }
    else{
        root=root->ch[0];
        root->fa=NULL;
        node *p=root;
        while(p->ch[1]) p=p->ch[1];
        p->ch[1]=x->ch[1];
        x->ch[1]->fa=p;
        splay(x->ch[1],NULL);
    }
    if(root) root->fa=NULL;
    Insert(x);
}
void del(node *x){
    if(x==NULL) return;
    del(x->ch[1]);
    del(x->ch[0]);
    delete x;
}
int Rank(int k){//求第k位置
   // node *pre=NULL;
    node *p=root;
    int l;
    while(1){
        l=0;
    if(p->ch[0]) l+=p->ch[0]->sz;
    if(l<k&&l+p->len>=k) break;
    else if(l>=k) p=p->ch[0];
    else {
            k-=l+p->len;
            p=p->ch[1];
    }
    }
    return p->v-p->len+(k-l);
}
node *rt[maxn];//儲存離散化後相應位置的位址
char s[maxn][10];//儲存詢問
int sn[maxn];
int f[maxn],fn;
map<int,int> h;//hash記錄儲存對應數字的節點
int main()
{
    int T,t,n,q,x;
    //char s[10];
    root=NULL;
    rd(T);t=0;
    while(T--){
        rd2(n,q);
        //del(root);
        root=NULL;
        fn=0;
        h.clear();
        for(int i=1;i<=q;i++){
            scanf("%s%d",s[i],&sn[i]);
            if(s[i][0]!='R') f[++fn]=sn[i];
        }
        f[++fn]=n;
        sort(f+1,f+1+fn);//離散化
        fn=unique(f+1,f+1+fn)-f-1;
        f[0]=0;
        for(int i=fn;i>=1;i--){//離散化插入到樹中
            node *p=new node();
            p->v=f[i];p->len=1;
            Insert(p);
            rt[i]=p;
            h[f[i]]=i;
            if(f[i]-f[i-1]>1){
                p=new node();
                p->v=f[i]-1;p->len=f[i]-f[i-1]-1;
                Insert(p);
            }
        }
        printf("Case %d:\n",++t);
        for(int i=1;i<=q;i++){
            //scanf("%s%d",s,&x);
            if(s[i][0]=='T'){
                node *p=rt[h[sn[i]]];
                Erase(p);
            }
            else if(s[i][0]=='Q'){
                    node *p=rt[h[sn[i]]];
                    splay(p,NULL);
                printf("%d\n",p->ch[0]==NULL?1:p->ch[0]->sz+1);
            }
            else{
                printf("%d\n",Rank(sn[i]));
            }
            /*for(int i=1;i<=n;i++){
                splay(rt[i],NULL);
                printf("%d %d\n",i,rt[i]->ch[0]==NULL?1:rt[i]->ch[0]->sz+1);
              //  printf("left %d\n",rt[i]->ch[0]==NULL?0:rt[i]->ch[0]->v);
                //printf("right %d\n",rt[i]->ch[1]==NULL?0:rt[i]->ch[1]->v);
            }*/
        }
        del(root);
    }
    return 0;
}