[洛谷P2596][ZJOI2006]书架

ゝ一世哀愁。 2023-06-05 12:40 8阅读 0赞

题目描述：[https://www.luogu.org/problem/P2596][https_www.luogu.org_problem_P2596]

解析：首先以位置建立splay。对于1操作，将x旋至根，将x的左儿子与该点的后继相连即可。对于2操作同理。对于3操作，若t为0，不变，其他本质上相当于该点与前或后交换位置。假设现在与前交换位置，可将该点旋至根，再将该点的前驱旋至该点的左儿子，互相交换即可。与后交换位置同理。对于4.5操作，直接找即可。

细节：1.当一个点变成另一个点的儿子时，一定要记得更新这个点的fa。2.每次相连操作或交换操作时，要记得更新size

附上代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<cstdio>
    #include<iostream>
    #include<map>
    #include<climits>
    using namespace std;
    
    const int MAXN=80005;
    int n,m;
    int val[MAXN];
    struct Node{
        int son[2],fa,size,val;
    }node[MAXN];
    int root;
    int ndnum=0;
    int mp[MAXN];
    
    inline int read(){
        int ret=0,f=1;char c=getchar();
        while(c<'0'||c>'9'){
         if(c=='-') f=-1;c=getchar();}
        while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
        return ret*f;
    }
    
    int new_node(int val){
        int x=++ndnum;
        node[x].fa=node[x].son[0]=node[x].son[1]=0;
        node[x].size=1;node[x].val=val;
        if(val>0) mp[val]=x;
        return x;
    }
    
    void update(int x){
        node[x].size=node[node[x].son[0]].size+node[node[x].son[1]].size+1;
    }
    
    int buildtree(int l,int r){
        if(l>r) return 0;
        if(l==r) return new_node(val[l]);
        int mid=(l+r)>>1,x=new_node(val[mid]);
        node[x].son[0]=buildtree(l,mid-1);node[x].son[1]=buildtree(mid+1,r);
        node[node[x].son[0]].fa=x;node[node[x].son[1]].fa=x;
        update(x);
        return x;
    }
    
    int check(int x){
        return x==node[node[x].fa].son[1];
    }
    
    void rotate(int x){
        int y=node[x].fa,z=node[y].fa,d=check(x),xx=node[x].son[d^1];
        node[y].son[d]=xx;node[xx].fa=y;
        node[z].son[check(y)]=x;node[x].fa=z;
        node[x].son[d^1]=y;node[y].fa=x;
        update(y);update(x);
    }
    
    void splay(int x,int to=0){
        while(node[x].fa!=to){
            int y=node[x].fa,z=node[y].fa;
            if(z!=to)
                rotate(check(x)==check(y)?y:x);
            rotate(x);
        }
        if(!to)
            root=x;
    }
    
    void move_to_first(int x){
        splay(x);
        if(!node[x].son[0]) return;
        if(!node[x].son[1]){
            swap(node[x].son[0],node[x].son[1]);
            return;
        }
        int lson=node[x].son[0],tmp=node[x].son[1];
        while(node[tmp].son[0]) tmp=node[tmp].son[0];
        node[lson].fa=tmp;node[tmp].son[0]=lson;node[x].son[0]=0;
        splay(lson);  
    }
    
    void move_to_last(int x){
        splay(x);
        if(!node[x].son[1]) return;
        if(!node[x].son[0]){
            swap(node[x].son[0],node[x].son[1]);
            return;
        }
        int rson=node[x].son[1],tmp=node[x].son[0];
        while(node[tmp].son[1]) tmp=node[tmp].son[1];
        node[rson].fa=tmp;node[tmp].son[1]=rson;node[x].son[1]=0;
        splay(rson);
    }
    
    void change(int x,int y){
        splay(x);
        if(y==-1){
            int lson=node[x].son[0];
            if(!lson) return;    
            while(node[lson].son[1]) lson=node[lson].son[1];
            splay(lson,x);
            int lson_lson=node[lson].son[0],lson_rson=node[lson].son[1];
            node[lson].son[0]=x;node[x].fa=lson;
            node[lson].son[1]=node[x].son[1];node[node[x].son[1]].fa=lson;
            node[x].son[0]=lson_lson;node[lson_lson].fa=x;
            node[x].son[1]=lson_rson;node[lson_rson].fa=x;
            node[lson].fa=0;
            update(x);update(lson);
            root=lson;
        } 
        if(y==1){
            int rson=node[x].son[1];
            if(!rson) return;
            while(node[rson].son[0]) rson=node[rson].son[0];
            splay(rson,x);
            int rson_lson=node[rson].son[0],rson_rson=node[rson].son[1];
            node[rson].son[0]=node[x].son[0];node[node[x].son[0]].fa=rson;
            node[rson].son[1]=x;node[x].fa=rson;
            node[x].son[0]=rson_lson;node[rson_lson].fa=x;
            node[x].son[1]=rson_rson;node[rson_rson].fa=x;
            node[rson].fa=0;
            update(x);update(rson);
            root=rson;
        }
    }
    
    int query(int x){
        splay(x);
        return node[node[x].son[0]].size;
    }
    
    int find(int kth){
        int cur=root;
        while(1){
            if(kth<=node[node[cur].son[0]].size)
                cur=node[cur].son[0];
            else{
                kth-=node[node[cur].son[0]].size+1;
                if(!kth) return cur;
                cur=node[cur].son[1];
            }
        }
    }
    
    void write(int x){
        if(node[x].son[0]) write(node[x].son[0]);
        cout<<node[x].val<<' ';
        if(node[x].son[1]) write(node[x].son[1]);
    }
    
    int main(){
        n=read();m=read();
        for(int i=1;i<=n;++i) val[i]=read();
        root=buildtree(1,n);
        while(m--){
            char opt[15];
            scanf("%s",opt+1);
            if(opt[1]=='T'){
                int x=read();
                move_to_first(mp[x]);
            }
            else if(opt[1]=='B'){
                int x=read();
                move_to_last(mp[x]);
            }
            else if(opt[1]=='I'){
                int x=read(),y=read();
                if(y==0) continue;
                change(mp[x],y);
            }
            else if(opt[1]=='A'){
                int x=read();
                printf("%d\n",query(mp[x]));
            }
            else{
                int x=read();
                printf("%d\n",node[find(x)].val);
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/JoshDun/p/11260904.html

[https_www.luogu.org_problem_P2596]: https://www.luogu.org/problem/P2596
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/a282d5ffb66e4fa8a621ad3bf015657d.png