P2596 [ZJOI2006]书架（splay）

[题目链接] https://www.luogu.org/problemnew/show/P2596

平衡树，需支持五个操作：

1、将某元素置顶：将元素旋到根，然后将左子树合并到该元素的后继

2、将某元素置底：将元素旋到根，然后将右子树合并到该元素的前驱

3、将某元素提前/滞后1位：直接与该元素的前驱/后继交换位置及信息

4、询问指定元素排名：将元素旋到根，输出size-1

5、询问指定排名元素：在树上find

必须维护每个点的位置,才能对它操作,不然找不到它

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int INF=1e9+7;

inline LL read(){

    register LL x=0,f=1;register char c=getchar();

    while(c<48||c>57){if(c=='-')f=-1;c=getchar();}

    while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();

    return f*x;

}

const int MAXN=80005;

namespace splay{

    int ch[MAXN][2],par[MAXN],num[MAXN],pos[MAXN],size[MAXN];

    int Ncnt,rt;

    inline bool chk(int x){

        return ch[par[x]][1]==x;

    }

    inline void pushup(int x){

        size[x]=size[ch[x][0]]+size[ch[x][1]]+1;

        pos[num[ch[x][0]]]=ch[x][0],pos[num[ch[x][1]]]=ch[x][1];

    }

    inline void rotate(int x){

        int y=par[x],z=par[y],k=chk(x),w=ch[x][k^1];

        ch[y][k]=w;par[w]=y;

        ch[z][chk(y)]=x;par[x]=z;

        ch[x][k^1]=y;par[y]=x;

        pushup(y);pushup(x);

    }

    inline void splay(int x,int goal=0){

        while(par[x]!=goal){

            int y=par[x],z=par[y];

            if(z!=goal){

                if(chk(x)==chk(y)) rotate(y);

                else rotate(x);

            }

            rotate(x);

        }

        if(!goal) rt=x;

    }

    inline void insert1(int val){

        ch[rt][1]=++Ncnt,num[Ncnt]=val,par[Ncnt]=rt,size[Ncnt]=1;//按顺序插入,直接放在最右边(中序遍历保证正确性)

        splay(Ncnt);

    }

    inline void top(int x){//旋到根节点,把左儿子接到它的后继

        splay(pos[x]);

        if(!ch[rt][0]) return;

        if(!ch[rt][1]) ch[rt][1]=ch[rt][0],ch[rt][0]=0;

        else{

            int suc=ch[rt][1];

            while(ch[suc][0]) suc=ch[suc][0];

            ch[suc][0]=ch[rt][0];

            par[ch[rt][0]]=suc;

            ch[rt][0]=0;

            splay(ch[suc][0]);

        }

    }

    inline void bottom(int x){//旋到根节点,把右儿子接到它的前驱

        splay(pos[x]);

        if(!ch[rt][1]) return;

        if(!ch[rt][0]) ch[rt][0]=ch[rt][1],ch[rt][1]=0;

        else{

            int pre=ch[rt][0];

            while(ch[pre][1]) pre=ch[pre][1];

            ch[pre][1]=ch[rt][1];

            par[ch[rt][1]]=pre;

            ch[rt][1]=0;

            splay(ch[pre][1]);

        }

    }

    inline void insert2(int x,int t){

        if(t==0) return;

        splay(pos[x]);

        if(t==1){

            int suc=ch[rt][1];

            while(ch[suc][0]) suc=ch[suc][0];

            int ps=pos[x];

            swap(pos[x],pos[num[suc]]);//交换信息

            swap(num[ps],num[suc]);

        }

        if(t==-1){

            int pre=ch[rt][0];

            while(ch[pre][1]) pre=ch[pre][1];

            int ps=pos[x];

            swap(pos[x],pos[num[pre]]);

            swap(num[ps],num[pre]);

        }

    }

    inline int kth(int k){

        int cur=rt;

        while(1){

            if(k<=size[ch[cur][0]]) cur=ch[cur][0];

            else if(k==size[ch[cur][0]]+1) return num[cur];

            else k-=size[ch[cur][0]]+1,cur=ch[cur][1];

        }

    }

    inline int query(int x){

        splay(pos[x]);

        return size[ch[rt][0]];

    }

}using namespace splay;

int n,m;

int main(){

    n=read(),m=read();

    for(int i=1;i<=n;i++) insert1(read());

    for(int i=1;i<=m;i++){

        char s[10];

        scanf("%s",s);

        switch (s[0]){

            case 'T': top(read()); break;

            case 'B': bottom(read()); break;

            case 'I':{

                int x=read(),y=read();

                insert2(x,y);

                break;

            }

            case 'Q': printf("%d\n",kth(read())); break;

            case 'A': printf("%d\n",query(read())); break;

        }

    }

}

巴特西

P2596 [ZJOI2006]书架（splay）

最新文章

热门文章