AT_arc030_4

· · 题解

看到这题，也不知道说啥好了。

看到很难维护的，按某种特定方式更改区间中的数的位置的，应该第一个考虑 FHQ-Treap。

可以发现，在全部操作中只有区间复制是最难的，它不能直接复制，因为它会改变原子树信息。不过，关于改变子树信息的，我们都可以考虑可持久化，于是原子树信息就不会被改变了，可以放心复制了。

最后要注意空间问题，如果快超出空间了，只要重构子树就好了。

Code

#include<bits/stdc++.h>
#define ll long long
#ifdef ONLINE_JUDGE
static char buf[4500000],*p1=buf,*p2=buf;
#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,4500000,stdin),p1==p2)?EOF:*p1++
#endif
inline int read(){bool f=0;int x=0;char c=getchar();while(!isdigit(c)) f|=c=='-',c=getchar();while(isdigit(c)) x=(x<<3)+(x<<1)+(c^48),c=getchar();return f?(~x+1):x;}
inline void write(ll x){if(x<0) putchar('-'),x=-x;static int sta[61];int top=0;do{sta[top++]=x%10,x/=10;}while(x);while(top) putchar(sta[--top]+'0');}
using namespace std;
const int N=2e5+5,M=1e7+5;
struct FHQ_Treap{
    int root,id,lb;ll b[N];
    struct node{int l,r,key,sz;ll sum,tag,val;}tr[M];
    inline int newnode(ll v=0){tr[++id]={0,0,rand(),1,v,0,v};return id;}
    inline void push_up(int p){tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+1;tr[p].sum=tr[tr[p].l].sum+tr[tr[p].r].sum+tr[p].val;}
    inline void ct(int p,ll v){tr[p].sum+=v*tr[p].sz;tr[p].val+=v;tr[p].tag+=v;}
    inline int copy_node(int x){int rt=++id;tr[rt]=tr[x];return rt;}
    inline void push_down(int p){
        if(tr[p].tag){
            if(tr[p].l) tr[p].l=copy_node(tr[p].l),ct(tr[p].l,tr[p].tag);
            if(tr[p].r) tr[p].r=copy_node(tr[p].r),ct(tr[p].r,tr[p].tag);
            tr[p].tag=0;
        }
    }inline void split(int p,int v,int &x,int &y){
        if(!p){x=y=0;return;}push_down(p);
        if(tr[tr[p].l].sz<v) x=copy_node(p),split(tr[x].r,v-tr[tr[x].l].sz-1,tr[x].r,y),push_up(x);
        else y=copy_node(p),split(tr[y].l,v,x,tr[y].l),push_up(y);
    }inline int merge(int x,int y){
        if(!x||!y) return x|y;int rt=++id;push_down(x);push_down(y);
        if(tr[x].key<tr[y].key){tr[rt]=tr[x];tr[rt].r=merge(tr[rt].r,y),push_up(rt);return rt;}
        else{tr[rt]=tr[y];tr[rt].l=merge(x,tr[rt].l),push_up(rt);return rt;}
    }inline void dfs(int x){if(x) push_down(x),dfs(tr[x].l),b[++lb]=tr[x].val,dfs(tr[x].r);}
    inline void pia(){lb=0,dfs(root),root=id=0;for(int i=1;i<=lb;i++) root=merge(root,newnode(b[i]));}
    inline void Modify(int l,int r,int v){int x,y,z;split(root,r,x,z);split(x,l-1,x,y);ct(y=copy_node(y),v);root=merge(merge(x,y),z);}
    inline void copy(int l,int r,int x,int y){int a,b,c,d,e,f;split(root,r,b,c);split(b,l-1,a,b);split(root,y,e,f);split(e,x-1,d,e);root=merge(merge(a,e),c);}
    inline ll Ask(int l,int r){int x,y,z;split(root,r,x,z);split(x,l-1,x,y);ll u=tr[y].sum;root=merge(merge(x,y),z);return u;}
}T;
int n,m,a[N],op,l,r,x,y;
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read(),T.root=T.merge(T.root,T.newnode(a[i]));
    while(m--){
        op=read(),l=read(),r=read();
        if(op==1) x=read(),T.Modify(l,r,x);
        else if(op==2) x=read(),y=read(),T.copy(l,r,x,y);
        else write(T.Ask(l,r)),putchar('\n');
        if(T.id>M-5e5) T.pia();
    }
    return 0;
}