NOI2005 维护数列

摘要

题意：维护一个数列支持 6 种操作：在某一位置插入 / 删除 / 覆盖 / 翻转 / 求和一段数字；求整个数列的最大的连续一段的数字的和。

既然这个序列的形态变化，自然想到平衡树维护。然后，我就调了 6 小时 emmm

打覆盖和翻转的标记的时侯，该下传的就下传，不要互相干涉（别问我为什么这么说）

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=5e5+5,M=2e4+4,NONE=23333,INF=0x3f3f3f3f;
int n,m;

const int SZ=N+M;
int seed=1,root,tot;
int ch[SZ][2],rnd[SZ],val[SZ];//val 是值
int sz[SZ],rev[SZ],tag[SZ],sum[SZ];
int sl[SZ],sr[SZ],ss[SZ];

int rrand(){return seed*=482711;}// 随机值
void pushup(int u){const int& l=ch[u][0],r=ch[u][1];
    sz[u]=sz[l]+sz[r]+1;
    sum[u]=sum[l]+sum[r]+val[u];
    // 因为保证 sum[0]==0 所以不用判断儿子
    sl[u]=max(sl[l],sum[l]+val[u]+max(0,sl[r]));
    sr[u]=max(sr[r],sum[r]+val[u]+max(0,sr[l]));
    ss[u]=max(max(ss[l],ss[r]),max(sr[l],0)+val[u]+max(sl[r],0));
}
void pushtag(int u,int tg,int rv){
    // 把 tg/rv 的 tag 施加到结点 u 上，并且使 u 的信息被 tag 更新
    if(tg!=NONE){val[u]=tg,sum[u]=sz[u]*tg;
        sl[u]=ss[u]=sr[u]=tg>0?sum[u]:tg;//!!!!!!!!!!!
        tag[u]=tg;// 不要随便动另外的标记，该下传就下传!!!!!
    }
    if(rv){swap(ch[u][0],ch[u][1]);
        swap(sl[u],sr[u]);//!!!!!!!!
        rev[u]^=1;
    }
}
void pushdown(int u){if(rev[u]){pushtag(ch[u][0],NONE,1), pushtag(ch[u][1],NONE,1);
        rev[u]=0;//!!!!!!!!!!
    }
    if(tag[u]!=NONE){pushtag(ch[u][0],tag[u],0), pushtag(ch[u][1],tag[u],0);
        tag[u]=NONE;//!!!!!!!!!
    }
}
queue<int> q;
int new_node(int v){// 建立值为 v 的新结点
    int u;
    if(q.empty())u=++tot;
    else u=q.front(),q.pop();
    ch[u][0]=ch[u][1]=rev[u]=0,tag[u]=NONE;
    sz[u]=1,rnd[u]=rrand(),val[u]=sum[u]=v;
    sl[u]=sr[u]=ss[u]=v;
    return u;
}
void del_tree(int u){// 回收以 u 为根的树的结点
    q.push(u);
    if(ch[u][0])del_tree(ch[u][0]);
    if(ch[u][1])del_tree(ch[u][1]);
}
void split(int u,int k,int &x,int &y){
    // 分割函数，这里的 k 是指把 u 的前 k 个数 split 出来成为 x
    if(!u){x=y=0;return;}
    pushdown(u);
    if(k>sz[ch[u][0]])x=u, split(ch[u][1],k-sz[ch[u][0]]-1,ch[u][1],y);
    else y=u, split(ch[u][0],k,x,ch[u][0]);
    pushup(u);// 递归完成后，向上更新
}
int merge(int x,int y){//x<y
    pushdown(x),pushdown(y);//!!!!!!!!
    if(!x||!y)return x+y;
    if(rnd[x]<rnd[y])return ch[x][1]=merge(ch[x][1],y), pushup(x), x;
    else return ch[y][0]=merge(x,ch[y][0]), pushup(y), y;
}
int build_tree(int *c,int l,int r){// 建立完全二叉树
    if(l>r)return 0;
    if(l==r)return new_node(c[l]);
    int mid=(l+r)>>1,u=new_node(c[mid]);
    ch[u][0]=build_tree(c,l,mid-1),ch[u][1]=build_tree(c,mid+1,r);
    pushup(u);
    return u;
}
void insert(int pos,int tot,int *c){//RT，插入函数
    int x,y,z;
    split(root,pos,x,y);
    z=build_tree(c,1,tot);
    x=merge(x,z);
    root=merge(x,y);
}
void del(int pos,int tot){//RT，删除函数
    int x,y,z;
    split(root,pos-1,x,y);
    split(y,tot,y,z);
    del_tree(y);
    root=merge(x,z);
}
void make_same(int pos,int tot,int c){//RT，覆盖操作
    int x,y,z;
    split(root,pos-1,x,y);
    split(y,tot,y,z);
    pushtag(y,c,0);
    root=merge(x,merge(y,z));
}
void reverse(int pos,int tot){//RT，翻转操作
    int x,y,z;
    split(root,pos-1,x,y);
    split(y,tot,y,z);
    pushtag(y,NONE,1);
    root=merge(x,merge(y,z));
}
int get_sum(int pos,int tot){//RT，求和函数
    int x,y,z,res;
    split(root,pos-1,x,y);
    split(y,tot,y,z);
    res=sum[y];
    root=merge(x,merge(y,z));
    return res;
}
int max_sum(){///RT，整个序列中和最大的连续的一段
    return ss[root];
}

int a[N],la;
int pos,tt,c[N];
int main(){ss[0]=sl[0]=sr[0]=-INF;//!!!!!!!!!!!
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    insert(0,n,a);// 插入 n 个数
    for(int i=1;i<=m;i++){char op[20];
        scanf("%s",op);
        if(op[0]=='I'){scanf("%d%d",&pos,&tt);
            for(int i=1;i<=tt;i++)scanf("%d",&c[i]);
            insert(pos,tt,c);
        }
        if(op[0]=='G'){scanf("%d%d",&pos,&tt);
            printf("%d\n",get_sum(pos,tt));
        }
        if(op[0]=='D'){scanf("%d%d",&pos,&tt);
            del(pos,tt);
        }
        if(op[0]=='M'&&op[2]=='X'){printf("%d\n",max_sum());
        }
        if(op[0]=='M'&&op[2]=='K'){scanf("%d%d%d",&pos,&tt,&c[0]);
            make_same(pos,tt,c[0]);
        }
        if(op[0]=='R'){scanf("%d%d",&pos,&tt);
            reverse(pos,tt);
        }
    }
    return 0;
}