【洛谷P5586】[P5350] 序列 (加强版)

Author Avatar
mrsrz 10月 14, 2019

可持久化平衡树

题目大意：

给定一个序列，需要支持以下操作：

  1. 给定 $l,r$，问 $a_l\sim a_r$ 的和。
  2. 给定 $l,r,k$，将 $a_l\sim a_r$ 都变为 $k$。
  3. 给定 $l,r,k$，将 $a_l\sim a_r$ 都加上 $k$。
  4. 给定 $l_1,r_1,l_2,r_2$，保证 $r_1-l_1=r_2-l_2$ 且 $[l_1,r_1]\bigcap[l_2,r_2]=\varnothing$，将 $a_{l_2}\sim a_{r_2}$ 对应的位置变成 $a_{l_1}\sim a_{r_1}$ 的对应位置。
  5. 给定 $l_1,r_1,l_2,r_2$，保证 $r_1-l_1=r_2-l_2$ 且 $[l_1,r_1]\bigcap[l_2,r_2]=\varnothing$，交换 $a_{l_1}\sim a_{r_1}$ 和 $a_{l_2}\sim a_{r_2}$ 。
  6. 给定 $l,r$，翻转 $a_l\sim a_r$。

强制在线，且数据不随机。

解题思路：

P5350 是数据随机，所以可以直接珂朵莉树。

本题数据不随机。考虑使用不依赖随机数据特性的数据结构求解。

对于操作 $1,2,3,6$，属于数据结构基本操作，可以使用平衡树解决。

对于操作 $5$，不难想到用支持分裂合并的平衡树，将两个区间分裂出来，交换位置后合并即可。

对于操作 $4$，我们如何在正确的复杂度下实现复制一段区间的操作？

可持久化可以满足要求。我们把整棵平衡树可持久化，执行操作 $4$ 的时候，把区间分裂出来，然后把需要复制的结点克隆一份，再合并上去即可。

我使用可持久化 Treap 实现。每个操作的期望复杂度都是 $O(\log n)$ 的。

有一些注意事项：

  1. 直接对每个结点赋一个随机值作为 $key$ 的做法复杂度会有问题，正确的做法是在合并的时候按照子树大小来随机合并。
  2. 可持久化时会消耗非常多的结点。当开不下的时候，需要定期对树进行重构。由于我们已经不需要给每个结点赋一个随机值了，所以可以直接按照线段树的建树方式 $O(n)$ 完成建树而不需要笛卡尔树。
  3. 可能会有些卡常……

总时间复杂度 $O(m\log n)$。

Code：

#include<cstdio>
#include<ctime>
#include<cctype>
#include<random>
#include<vector>
#include<algorithm>
using namespace std;
const int N=3e5+6,md=1e9+7;
typedef long long LL;
mt19937 mt(time(0));
inline void upd(int&a){a+=a>>31&md;}
char buf[(int)1e8],*ss=buf;
inline int InIt(){buf[fread(buf,1,(int)1e8-1,stdin)]='\n';return 0;}
const int __START__=InIt();
inline int readint(){
    int d=0;
    while(!isdigit(*ss))++ss;
    while(isdigit(*ss))d=d*10+(*ss++^'0');
    return d;
}
namespace T{
    const int M=8e6+6;
    int val[M],d[M],ls[M],rs[M],sz[M],cov[M],add[M];bool tag[M];
    int id,n,rt;
    inline int newnode(int a){
        d[++id]=a,val[id]=a;ls[id]=rs[id]=add[id]=0,sz[id]=1,tag[id]=0;
        cov[id]=-1;
        return id;
    }
    inline int clone(int x){
        ++id;
        val[id]=val[x],d[id]=d[x],ls[id]=ls[x],rs[id]=rs[x],sz[id]=sz[x],cov[id]=cov[x],add[id]=add[x];
        tag[id]=tag[x];
        return id;
    }
    inline void flip(int x){
        swap(ls[x],rs[x]),tag[x]^=1;
    }
    inline void cover(int x,int v){
        cov[x]=v,d[x]=(LL)v*sz[x]%md,val[x]=v,add[x]=0;
    }
    inline void inc(int x,int v){
        upd(add[x]+=v-md),d[x]=(d[x]+(LL)v*sz[x])%md,upd(val[x]+=v-md);
    }
    inline void update(int x){
        sz[x]=sz[ls[x]]+sz[rs[x]]+1,upd(d[x]=d[ls[x]]+d[rs[x]]-md),upd(d[x]+=val[x]-md);
    }
    inline void pushdown(int x){
        if(ls[x])ls[x]=clone(ls[x]);
        if(rs[x])rs[x]=clone(rs[x]);
        if(tag[x]){
            tag[x]=0;
            if(ls[x])flip(ls[x]);
            if(rs[x])flip(rs[x]);
        }
        if(cov[x]!=-1){
            if(ls[x])cover(ls[x],cov[x]);
            if(rs[x])cover(rs[x],cov[x]);
            cov[x]=-1;
        }
        if(add[x]){
            if(ls[x])inc(ls[x],add[x]);
            if(rs[x])inc(rs[x],add[x]);
            add[x]=0;
        }
    }
    inline int merge(int x,int y){
        if(!x||!y)return x|y;
        pushdown(x),pushdown(y);
        int u;
        if(mt()%(sz[x]+sz[y])<sz[x]){
            u=clone(x);
            rs[u]=merge(rs[x],y);
        }else{
            u=clone(y);
            ls[u]=merge(x,ls[y]);
        }
        update(u);
        return u;
    }
    inline void split(int u,int k,int&x,int&y){
        if(k==0)
            x=0,y=clone(u);
        else
            if(k==sz[u])x=clone(u),y=0;
            else{
                pushdown(u);
                if(k<=sz[ls[u]]){
                    y=clone(u);
                    split(ls[y],k,x,ls[y]);
                    update(y);
                }else{
                    x=clone(u);
                    split(rs[x],k-sz[ls[u]]-1,rs[x],y);
                    update(x);
                }
            }
    }
    void init(int&u,vector<int>&vc,int l,int r){
        if(l>r){u=0;return;}
        if(l==r){
            u=newnode(vc[l]);
            return;
        }
        const int mid=l+r>>1;
        u=newnode(vc[mid]);
        init(ls[u],vc,l,mid-1),init(rs[u],vc,mid+1,r);
        update(u);
    }
    void build(vector<int>&vc){
        n=vc.size();
        rt=id=0;
        init(rt,vc,0,n-1);
    }
    inline int query(int l,int r){
        int x,y,z;
        split(rt,r,x,z);
        split(x,l-1,x,y);
        return d[y];
    }
    inline void assign(int l,int r,int k){
        int x,y,z;
        split(rt,r,x,z);
        split(x,l-1,x,y);
        cover(y,k);
        rt=merge(merge(x,y),z);
    }
    inline void modify(int l,int r,int k){
        int x,y,z;
        split(rt,r,x,z);
        split(x,l-1,x,y);
        inc(y,k);
        rt=merge(merge(x,y),z);
    }
    inline void copyto(int l1,int r1,int l2,int r2){
        int tag=0;
        if(l1>l2)swap(l1,l2),swap(r1,r2),tag=1;
        int _1,_2,_3,_4,_5;
        split(rt,r2,rt,_5);
        split(rt,l2-1,rt,_4);
        split(rt,r1,rt,_3);
        split(rt,l1-1,_1,_2);
        if(tag)
            _2=clone(_4);
        else
            _4=clone(_2);
        rt=merge(merge(merge(merge(_1,_2),_3),_4),_5);
    }
    inline void swap_(int l1,int r1,int l2,int r2){
        if(l1>l2)swap(l1,l2),swap(r1,r2);
        int _1,_2,_3,_4,_5;
        split(rt,r2,rt,_5);
        split(rt,l2-1,rt,_4);
        split(rt,r1,rt,_3);
        split(rt,l1-1,_1,_2);
        rt=merge(merge(merge(merge(_1,_4),_3),_2),_5);
    }
    inline void rotate(int l,int r){
        int x,y,z;
        split(rt,r,x,z);
        split(x,l-1,x,y);
        flip(y);
        rt=merge(merge(x,y),z);
    }
    void dfs(int u,vector<int>&vc){
        if(!u)return;
        pushdown(u);
        dfs(ls[u],vc);
        vc.push_back(val[u]);
        dfs(rs[u],vc);
    }
    inline void get_list(vector<int>&vc){
        vc.clear();
        dfs(rt,vc);
    }
    inline bool dangerous(){
        return id>7.5e6;
    }
    inline void rebuild(){
        static vector<int>vc;
        vc.clear();
        get_list(vc);
        build(vc);
    }
}
int n,q;
int main(){
    n=readint(),q=readint();
    vector<int>vc;
    for(int i=1;i<=n;++i)
        vc.push_back(readint());
    T::build(vc);
    int lst=0;
    while(q--){
        int op=readint();
        switch(op){
            case 1:{
                       int l=readint(),r=readint();
                       l^=lst,r^=lst;
                       printf("%d\n",lst=T::query(l,r));
                       break;
                   }
            case 2:{
                       int l=readint(),r=readint(),k=readint();
                       l^=lst,r^=lst,k^=lst;
                       T::assign(l,r,k);
                       break;
                   }
            case 3:{
                       int l=readint(),r=readint(),k=readint();
                       l^=lst,r^=lst,k^=lst;
                       T::modify(l,r,k);
                       break;
                   }
            case 4:{
                       int l1=readint(),r1=readint(),l2=readint(),r2=readint();
                       l1^=lst,r1^=lst,l2^=lst,r2^=lst;
                       T::copyto(l1,r1,l2,r2);
                       break;
                   }
            case 5:{
                       int l1=readint(),r1=readint(),l2=readint(),r2=readint();
                       l1^=lst,r1^=lst,l2^=lst,r2^=lst;
                       T::swap_(l1,r1,l2,r2);
                       break;
                   }
            case 6:{
                       int l=readint(),r=readint();
                       l^=lst,r^=lst;
                       T::rotate(l,r);
                   }
        }
        if(T::dangerous())
            T::rebuild();
    }
    T::get_list(vc);
    for(int i:vc)
        printf("%d ",i);
    putchar('\n');
    return 0;
}
Powered by Hexo
Theme - Material