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;
}