[洛谷P3295][SCOI2014]方伯伯的OJ

迷南。 2023-06-05 12:40 4阅读 0赞

题目描述：[https://www.luogu.org/problemnew/show/P3285][https_www.luogu.org_problemnew_show_P3285]

解析：首先发现n的范围很大，但m的范围很小，所以被操作的点最多只有1e5个点，于是想到用一个点表示一段区间，要用的时候再拆开。怎么实现呢？想到用一颗平衡树来维护排名，每一个节点记录在原序列中的一段区间的左端点和右端点，用map来维护一段区间的右端点所在节点的编号，这样做就可以快速找到一个值所在splay中的节点编号。这样1操作就可以很顺利的解决了，记得拆开点之后要更新每个节点的L和R以及与m的更新。对于2操作，可先将该节点splay至根，再将根的左儿子直接连向该点的后继，最后将后继的左儿子转到根，这样既能更新子树的大小又能保证时间复杂度。3操作与2同理。对于4操作，直接查k大就可以了。

细节：好像没什么细节，不要写挂就好。

附上代码：

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

#include<cstdio>
    #include<iostream>
    #include<map>
    #include<algorithm>
    using namespace std;
    
    const int MAXM=1e5+5;
    int n,m;
    struct Node{
        int size,l,r,fa,son[2];
    }node[MAXM<<1];
    map<int,int> mp;
    int root;
    int ndnum=0;
    int ans=0;
    
    inline int read(){
        int ret=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9') {
         if (ch=='-') f=-f;ch=getchar();}
        while(ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
        return ret*f;
    }
    
    int new_node(int l,int r){
        int x=++ndnum;
        node[x].fa=node[x].son[0]=node[x].son[1]=0;
        node[x].l=l;node[x].r=r;
        node[x].size=node[x].r-node[x].l+1;
        return x;
    }
    
    void update(int x){
        int lson=node[x].son[0],rson=node[x].son[1];
        node[x].size=node[lson].size+node[rson].size+node[x].r-node[x].l+1;
    }
    
    void split(int pos,int x){
        int lson=0,rson=0; 
        if(node[pos].l==node[pos].r) return;
        mp[x]=pos;
        if(node[pos].l!=x){
            lson=mp[x-1]=new_node(node[pos].l,x-1);
            node[lson].fa=pos;
            node[lson].son[0]=node[pos].son[0];
            node[node[lson].son[0]].fa=lson;
            node[pos].son[0]=lson;
            node[pos].size=1;
        }
        if(node[pos].r!=x){
            rson=mp[node[pos].r]=new_node(x+1,node[pos].r);
            node[rson].fa=pos;
            node[rson].son[1]=node[pos].son[1];
            node[node[rson].son[1]].fa=rson;
            node[pos].son[1]=rson;
            node[pos].size=1;
        }
        node[pos].l=node[pos].r=x;
        if(lson) update(lson);
        if(rson) update(rson);
        update(pos);
    }
    
    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){
                if(check(x)==check(y)) rotate(y);
                 else rotate(x);
             }
             rotate(x);
        }
        if(!to) root=x;
    }
    
    int rank(int x){
        splay(x);
        return node[node[root].son[0]].size+1;
    }
    
    void merge(int x){
        splay(x);
        if(!node[x].son[0]) return;
        else if(!node[x].son[1]) {swap(node[x].son[0],node[x].son[1]);return;}
        else{
            int cur=node[x].son[1];
            while(node[cur].son[0]) cur=node[cur].son[0];
            int lson=node[x].son[0];
            node[lson].fa=cur;
            node[cur].son[0]=lson;
            node[x].son[0]=0;
            update(node[x].son[1]);update(x);
            splay(lson);
        }
    }
    
    void fmerge(int x){
        splay(x);
        if(!node[x].son[1]) return;
        else if(!node[x].son[0]) {swap(node[x].son[0],node[x].son[1]);return;}
        else{
            int cur=node[x].son[0];
            while(node[cur].son[1]) cur=node[cur].son[1];
            int rson=node[x].son[1];
            node[rson].fa=cur;
            node[cur].son[1]=rson;
            node[x].son[1]=0;
            update(node[x].son[0]);update(x);
            splay(rson);
        }
    }
    
    int find(int kth){
        int cur=root;
        while(1){
            int lson=node[cur].son[0],rson=node[cur].son[1];
            if(kth<=node[lson].size)
                cur=lson;
            else if(kth>node[lson].size+node[cur].r-node[cur].l+1){
                kth-=node[lson].size+node[cur].r-node[cur].l+1;
                cur=rson;
            }
            else{
                kth-=node[lson].size;
                return node[cur].l+kth-1;
            }
        }
    }
    
    int main(){
        n=read();m=read();
        mp[n]=root=new_node(1,n);
        for(int i=1;i<=m;i++){
            int opt=read();
            if(opt==1){
                int x=read(),y=read();
                x-=ans;y-=ans;
                int pos=(*mp.lower_bound(x)).second;
                split(pos,x);
                ans=rank(pos);
                node[pos].l=node[pos].r=y;
                mp[y]=pos;
                printf("%d\n",ans);
            }
            if(opt==2){
                int x=read();
                x-=ans;
                int pos=(*mp.lower_bound(x)).second;
                split(pos,x);
                ans=rank(pos);
                merge(pos);
                printf("%d\n",ans);
            }
            if(opt==3){
                int x=read();
                x-=ans;
                int pos=(*mp.lower_bound(x)).second;
                split(pos,x);
                ans=rank(pos);
                fmerge(pos);
                printf("%d\n",ans);
            }
            if(opt==4){
                int x=read();
                x-=ans; 
                ans=find(x);
                printf("%d\n",ans);
            }
        }
        return 0;
    }

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

[https_www.luogu.org_problemnew_show_P3285]: https://www.luogu.org/problemnew/show/P3285
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/352b2a75e8ba4b2ea5447183e30a3d63.png