题解：P5586 [P5350] 序列 (加强版)

cheng2010 · 2024-05-06 19:26:15 · 题解

序列 (加强版)

思路：

做过这题的同学，想必对于对于区间求和、赋值、加值、交换、翻转操作都可以很轻松地使用平衡树进行维护，那么如何复制一段区间？

可以考虑可持久化。因为，把两段区间分裂出来后（根设为 r1 和 r2）如果直接把 r2 变为 r1 那么后续的操作都会被重复，肯定会答案错误，而暴力复制的话肯定会超时，所以，只有可持久化，提前复制出来才行。

注意：

不卡空间是鰰的谎言，要定期重构，当节点数达到临界值时，就要重构，否则就会爆炸。

code

#include<bits/stdc++.h>
#define ls(x) tree[x].lson
#define rs(x) tree[x].rson
#define Mod 1000000007
using namespace std;
const int N=5e5+7;
const int M=5e6+7;
const int MAXN=3e6+7;
int n,q;
int m;
int a[N];
struct FHQ_Treap
{
    int sum,val,siz,lson,rson;
    int fug,add,rev,rnd;
}tree[M];
struct FHQ_TREAP
{
    int cnt;
    int root;
    inline int add(int a,int b){return a+b>=Mod?a+b-Mod:a+b;}
    inline void update(int now)
    {
        tree[now].siz=tree[ls(now)].siz+1+tree[rs(now)].siz;
        tree[now].sum=add(add(tree[ls(now)].sum,tree[rs(now)].sum),tree[now].val);
    }
    inline int copy(int now)
    {
        tree[++cnt]=tree[now];
        return cnt;
    }
    inline void Rev(int now)
    {
        swap(ls(now),rs(now));
        tree[now].rev^=1;
    }
    inline void Add(int now,int k)
    {
        tree[now].val=add(tree[now].val,k);
        tree[now].add=add(tree[now].add,k);
        tree[now].sum=add(tree[now].sum,1ll*tree[now].siz*k%Mod);
    }
    inline void Cov(int now,int k)
    {
        tree[now].add=0;
        tree[now].fug=tree[now].val=k;
        tree[now].sum=1ll*tree[now].siz*k%Mod;
    }
    inline void down(int now)
    {
        if(tree[now].add||tree[now].fug!=-1||tree[now].rev)
        {
            if(ls(now)) ls(now)=copy(ls(now));
            if(rs(now)) rs(now)=copy(rs(now));
        }
        if(tree[now].fug!=-1)
        {
            if(ls(now)) Cov(ls(now),tree[now].fug);
            if(rs(now)) Cov(rs(now),tree[now].fug);
            tree[now].fug=-1; 
        }
        if(tree[now].add)
        {
            if(ls(now)) Add(ls(now),tree[now].add);
            if(rs(now)) Add(rs(now),tree[now].add);
            tree[now].add=0;
        }
        if(tree[now].rev)
        {
            if(ls(now)) Rev(ls(now));
            if(rs(now)) Rev(rs(now));
            tree[now].rev=0;
        }
    }
    inline void split(int now,int key,int &x,int &y)
    {
        if(!now)
        {
            x=y=0;
            return;
        }
        down(now);
        if(tree[ls(now)].siz+1<=key)
        {
            x=copy(now);
            split(rs(x),key-1-tree[ls(x)].siz,rs(x),y);
            update(x);
        }
        else
        {
            y=copy(now);
            split(ls(y),key,x,ls(y));
            update(y);
        }
    }
    inline int merge(int x,int y)
    {
        if(!x||!y) return x|y;
        if(tree[x].rnd<tree[y].rnd)
        {
            x=copy(x);
            down(x);
            rs(x)=merge(rs(x),y);
            update(x);
            return x; 
        }
        y=copy(y);
        down(y);
        ls(y)=merge(x,ls(y));
        update(y);
        return y;
    }
    inline int join(int x)
    {
        tree[++cnt].rnd=rand();
        tree[cnt].siz=1;
        tree[cnt].val=x;
        tree[cnt].sum=x;
        tree[cnt].fug=-1;
        return cnt;
    }
    inline int build(int l,int r)
    {
        int mid=l+r>>1;
        int now=join(a[mid]);
        if(l>r) return 0;
        ls(now)=build(l,mid-1);
        rs(now)=build(mid+1,r);
        update(now);
        return now;
    }
    inline int query(int l,int r)
    {
        int r1,r2,r3,ans;
        split(root,r,r1,r3);
        split(r1,l-1,r1,r2);
        ans=tree[r2].sum;
        root=merge(merge(r1,r2),r3);
        return ans;
    }
    inline void cover(int l,int r,int k)
    {
        int r1,r2,r3;
        split(root,r,r1,r3);
        split(r1,l-1,r1,r2);
        Cov(r2,k);
        root=merge(merge(r1,r2),r3);
    }
    inline void change(int l,int r,int k)
    {
        int r1,r2,r3;
        split(root,r,r1,r3);
        split(r1,l-1,r1,r2);
        Add(r2,k);
        root=merge(merge(r1,r2),r3);
    }
    inline void reverse(int l,int r)
    {
        int r1,r2,r3;
        split(root,r,r1,r3);
        split(r1,l-1,r1,r2);
        Rev(r2);
        root=merge(merge(r1,r2),r3);
    }
    inline void Copy(int l1,int ri1,int l2,int ri2)
    {
        int r1,r2,r3,r4,r5,fu=0;
        if(l1>l2)
        {
            swap(l1,l2);
            swap(ri1,ri2);
            fu=1;
        }
        split(root,ri2,r1,r5);
        split(r1,l2-1,r1,r4);
        split(r1,ri1,r1,r3);
        split(r1,l1-1,r1,r2);
        if(!fu) r4=copy(r2);
        else r2=copy(r4);
        root=merge(merge(merge(merge(r1,r2),r3),r4),r5);
    }
    inline void Swap(int l1,int ri1,int l2,int ri2)
    {
        int r1,r2,r3,r4,r5;
        if(l1>l2)
        {
            swap(l1,l2);
            swap(ri1,ri2);
        }
        split(root,ri2,r1,r5);
        split(r1,l2-1,r1,r4);
        split(r1,ri1,r1,r3);
        split(r1,l1-1,r1,r2);
        root=merge(merge(merge(merge(r1,r4),r3),r2),r5);
    }
    inline void flush(int now)
    {
        down(now);
        if(ls(now)) flush(ls(now));
        a[++m]=tree[now].val;
        if(rs(now)) flush(rs(now));
    }
}Tree;
int lst;
signed main()
{
    srand(time(NULL));
    scanf("%d %d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    Tree.root=Tree.build(1,n);
    while(q--)
    {
        int opt,l1,r1,l2,r2,k;
        scanf("%d %d %d",&opt,&l1,&r1);
        l1^=lst;
        r1^=lst;
        if(opt==1)
        {
            lst=Tree.query(l1,r1);
            printf("%d\n",lst);
        }
        else if(opt==2)
        {
            scanf("%d",&k);
            k^=lst;
            Tree.cover(l1,r1,k);
        }
        else if(opt==3)
        {
            scanf("%d",&k);
            k^=lst;
            Tree.change(l1,r1,k);
        }
        else if(opt==4)
        {
            scanf("%d %d",&l2,&r2);
            l2^=lst;
            r2^=lst;
            Tree.Copy(l1,r1,l2,r2);
        }
        else if(opt==5)
        {
            scanf("%d %d",&l2,&r2);
            l2^=lst;
            r2^=lst;
            Tree.Swap(l1,r1,l2,r2);
        }
        else
        {
            Tree.reverse(l1,r1);
        }
        if(Tree.cnt>MAXN)
        {
            m=0;
            Tree.flush(Tree.root);
            Tree.root=Tree.cnt=0;
            Tree.root=Tree.build(1,n);
        }
    }
    m=0;
    Tree.flush(Tree.root);
    for(int i=1;i<=n;i++)
        printf("%d ",a[i]);
}