P5586 题解

· · 题解

给出一种时间复杂度不变但线性空间的做法。

思考为什么可持久化平衡树就可以完成区间复制，因为可持久化后修改不会导致原版本被修改，因此可以直接复制。

但可持久化对空间有巨大的消耗，考虑使用引用计数（现代对于多个字符串处理的常见方式）。

也就是说我们尽可能把相同的内容使用同一块空间表示，当进行修改时如果引用不为 一 就进行复制。当引用为零时即可删除节点。

复杂度：

时间：

因为每次我们只会访问 \log n 个节点，此时才可能发生复制。复制带来的总节点数量 O(n \log n)。

删除的时候每删除一个节点的复杂度为 O(1) 删除节点数量不可能超过总结点数量 因此删除带来的总复杂度同样为 O(n \log n)。

空间：

考虑总引用次数不超过 O(n)，因此在每个时刻节点总个数不超过 O(n)。

实现上：

我们额外记录一个该点被引用的次数，根节点固定为一，此外每个节点引用一次它的左右孩子。

那么在没有区间复制时每个节点的引用计数都为一。

现在我们对它进行区间复制。

要复制的那个区间因为此时不涉及修改只需要把它的引用次数增加一次，然后合并。

被复制的那个区间的引用计数减少一次，如果发现引用次数已经为零就递归删除。

注意打标记时有修改因此检查是否要复制。

//HAVE WE BECOME BLASPHEMOUS?
#include<bits/stdc++.h>
using i64=long long;
constexpr int mod=1e9+7,maxn=3e5+50;
int rand01(i64 x,i64 y){
    return y*rand()<x*RAND_MAX;
}//x/y的几率返回1 否则返回0
struct FHQtreap{
    struct Node{
        i64 sum,val,add,set;
        int l,r,siz,rev,ref;
        inline void Set(i64 v){val=set=v,sum=v*siz,add=0;}
        inline void Add(i64 v){add+=v,sum+=v*siz,val+=v;}
        inline void Rev(){std::swap(l,r),rev^=1;}
    }tr[maxn];//FHQtreap的节点
    int cnt,bin[maxn],top,root;
    //使用的节点总数 垃圾桶 垃圾桶顶 根节点id
    inline void delid(int id){bin[++top]=id;}
    int newid(){return top?bin[top--]:++cnt;}
    inline int newnode(i64 val){
        int id=newid();
        tr[id]={val,val,0,-1,0,0,1,0,1};
        return id;
    }//新建一个对应权值的节点并返回其编号
    #define ls tr[rt].l
    #define rs tr[rt].r
    void Kill(int rt){
        if(!rt){return ;}
        if(tr[rt].ref>1){return --tr[rt].ref,void();}
        Kill(ls),Kill(rs),delid(rt);
    }//删除以rt为根的节点
    inline void pushup(int rt){
        tr[rt].sum=tr[ls].sum+tr[rt].val+tr[rs].sum;
        tr[rt].siz=tr[ls].siz+1+tr[rs].siz;
    }
    inline void check(int &rt){
        if(tr[rt].ref>1){
            int nw=newid();
            (tr[nw]=tr[rt]).ref=1,--tr[rt].ref,rt=nw;
            if(ls)++tr[ls].ref;
            if(rs)++tr[rs].ref;
        }
    }//检测是否引用大于1 (copy on write)
    inline void pushdown(int &rt){
        check(rt);
        if(~tr[rt].set){
            if(ls)check(ls),tr[ls].Set(tr[rt].set);
            if(rs)check(rs),tr[rs].Set(tr[rt].set);
            tr[rt].set=-1;
        }
        if(tr[rt].rev){
            if(ls)check(ls),tr[ls].Rev();
            if(rs)check(rs),tr[rs].Rev();
            tr[rt].rev=0;
        }
        if(tr[rt].add){
            if(ls)check(ls),tr[ls].Add(tr[rt].add);
            if(rs)check(rs),tr[rs].Add(tr[rt].add);
            tr[rt].add=0;
        }
    }//下传 保证不冲突
    void split(int rt,int k,int &x,int &y){
        if(!rt){return x=y=0,void();}
        pushdown(rt);
        if(tr[ls].siz<k){
            x=rt,split(rs,k-tr[ls].siz-1,rs,y);
            pushup(x);
        }
        else{
            y=rt,split(ls,k,x,ls);
            pushup(y);
        }
    }
    int merge(int x,int y){
        if(!x){return y;}
        if(!y){return x;}
        pushdown(x),pushdown(y);
        if(rand01(tr[x].siz,tr[y].siz+tr[x].siz)){
            tr[x].r=merge(tr[x].r,y),pushup(x);
            return x;
        }
        else{
            tr[y].l=merge(x,tr[y].l),pushup(y);
            return y;
        }
    }
    void print(int rt){
        if(!rt){return ;}
        pushdown(rt);
        print(ls),std::cout<<tr[rt].val%mod<<' ',print(rs);
    }//中序遍历即为打印这个序列
    #undef ls
    #undef rs
    i64 Sum(int l,int r){
        int x,y,z;
        split(root,r,x,z),split(x,l-1,x,y);
        i64 res=tr[y].sum;
        root=merge(merge(x,y),z);
        return res;
    }//获取区间和
    void Assign(int l,int r,i64 v){
        int x,y,z;
        split(root,r,x,z),split(x,l-1,x,y);
        check(y),tr[y].Set(v);
        root=merge(merge(x,y),z);
    }//区间赋值
    void Add(int l,int r,i64 v){
        int x,y,z;
        split(root,r,x,z),split(x,l-1,x,y);
        check(y),tr[y].Add(v);
        root=merge(merge(x,y),z);
    }//区间加
    void Copy(int l1,int r1,int l2,int r2){
        int con=0,v,w,x,y,z;
        if(l1>l2){
            std::swap(l1,l2),std::swap(r1,r2);
            con=1;
        }
        split(root,r2,v,z),split(v,l2-1,v,y);
        split(v,r1,v,x),split(v,l1-1,v,w);
        if(con){
            std::swap(w,y);
        }
        tr[w].ref++;
        if(tr[y].ref>1){--tr[y].ref;}else{Kill(y);}
        root=merge(v,merge(w,merge(x,merge(w,z)))); 
    }//区间复制
    void Swap(int l1,int r1,int l2,int r2){
        if(l1>l2){std::swap(l1,l2),std::swap(r1,r2);}
        int v,w,x,y,z;
        split(root,r2,v,z),split(v,l2-1,v,y);
        split(v,r1,v,x),split(v,l1-1,v,w);
        root=merge(v,merge(y,merge(x,merge(w,z))));
    }//区间交换
    void Reverse(int l,int r){
        int x,y,z;
        split(root,r,x,z),split(x,l-1,x,y);
        check(y),tr[y].Rev();
        root=merge(merge(x,y),z);
    }//区间翻转
}T;
void solve(){
    int n,q;
    std::cin>>n>>q;
    for(int i=0,x;i!=n;i++){
        std::cin>>x;
        T.root=T.merge(T.root,T.newnode(x));
    }
    for(int i=0,op,l,r,x,y,las=0;i!=q;i++){
        std::cin>>op>>l>>r,l^=las,r^=las;
        switch(op){
            case 1:std::cout<<(las=T.Sum(l,r)%mod)<<'\n';break;
            case 2:std::cin>>x,x^=las;T.Assign(l,r,x);break;
            case 3:std::cin>>x,x^=las;T.Add(l,r,x);break;
            case 4:std::cin>>x>>y,x^=las,y^=las;T.Copy(l,r,x,y);break;
            case 5:std::cin>>x>>y,x^=las,y^=las;T.Swap(l,r,x,y);break;
            case 6:T.Reverse(l,r);break;
        }
    }
    T.print(T.root);
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    std::cerr<<"T.cnt:"<<T.cnt<<std::endl;
    return 0;
}