最大序列和小白逛公园做过
区间修改的优先级高于区间翻转的优先级（之前有题01串翻转）
序列维护平衡树 平衡树维护的是下标 因此中序遍历就是原序列
每个结点维护的都是结点 不像线段树可以维护区间 所以build 的操作有一些不一样
这题还卡空间 所以要弄一个简单的回收操作
注意up的顺序 必须从下到上 因为这个wa了好久
非常好（难调）的平衡树题
#include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);--i) #define ll long long #define see(x) (cerr<<(#x)<<'='<<(x)<<endl) #define pb push_back #define inf 0x3f3f3f3f #define CLR(A,v) memset(A,v,sizeof A) typedef pair<int,int>pii; ////////////////////////////////// const int N=2e6+10; queue<int>q; int lmax[N],rmax[N],siz[N],son[N][2],id[N],sum[N],maxans[N],fa[N],lson,rson,col[N],rev[N],root,v[N],ncnt,a[N],m,n; int chk(int x) { return son[fa[x]][1]==x; } void up(int pos) { lson=son[pos][0],rson=son[pos][1]; sum[pos]=sum[lson]+sum[rson]+v[pos]; siz[pos]=siz[lson]+siz[rson]+1; lmax[pos]=max(lmax[lson],sum[lson]+v[pos]+lmax[rson]); rmax[pos]=max(rmax[rson],sum[rson]+v[pos]+rmax[lson]); maxans[pos]=max(max(maxans[lson],maxans[rson]),v[pos]+rmax[lson]+lmax[rson]); } void down(int pos) { lson=son[pos][0];rson=son[pos][1]; if(col[pos]) { col[pos]=rev[pos]=0;//要删除区间翻转操作 if(lson)col[lson]=1,v[lson]=v[pos],sum[lson]=v[pos]*siz[lson]; if(rson)col[rson]=1,v[rson]=v[pos],sum[rson]=v[pos]*siz[rson]; if(v[pos]>=0) { if(lson)maxans[lson]=rmax[lson]=lmax[lson]=sum[lson]; if(rson)maxans[rson]=rmax[rson]=lmax[rson]=sum[rson]; } else { if(lson)lmax[lson]=rmax[lson]=0,maxans[lson]=v[pos]; if(rson)lmax[rson]=rmax[rson]=0,maxans[rson]=v[pos]; } } if(rev[pos]) { rev[pos]=0; rev[lson]^=1;rev[rson]^=1; swap(lmax[lson],rmax[lson]); swap(lmax[rson],rmax[rson]); swap(son[lson][0],son[lson][1]); swap(son[rson][0],son[rson][1]); } } void rotate(int x) { int y=fa[x],z=fa[y],k=chk(x),w=son[x][k^1]; son[y][k]=w;fa[w]=y; son[z][chk(y)]=x;fa[x]=z; son[x][k^1]=y;fa[y]=x; up(y);up(x);//up必须自下往上的 我这里写成up(x),up(y)就一直wa } void splay(int x,int goal=0) { while(fa[x]!=goal) { int y=fa[x],z=fa[y]; if(z!=goal) { if(chk(x)==chk(y))rotate(y); else rotate(x); } rotate(x); } if(!goal)root=x; } int find1(int x,int k) { down(x); if(siz[son[x][0]]+1==k)return x; if(siz[son[x][0]]>=k)return find1(son[x][0],k); else return find1(son[x][1],k-siz[son[x][0]]-1); } void recycle(int x) { if(son[x][0])recycle(son[x][0]); if(son[x][1])recycle(son[x][1]); q.push(x); son[x][0]=son[x][1]=col[x]=rev[x]=fa[x]=0; } int split(int k,int tot) { int x=find1(root,k),y=find1(root,k+tot+1); splay(x);splay(y,x); return son[son[root][1]][0]; } int qsum(int k,int tot) { return sum[split(k,tot)]; } void upsum(int k,int tot,int val) { int x=split(k,tot); int y=fa[x]; col[x]=1; v[x]=val;sum[x]=siz[x]*val; if(v[x]>=0)maxans[x]=lmax[x]=rmax[x]=sum[x]; else lmax[x]=rmax[x]=0,maxans[x]=val; up(y);up(fa[y]); } void rever(int k,int tot) { int x=split(k,tot),y=fa[x]; if(!col[x]) { rev[x]^=1; swap(son[x][0],son[x][1]); swap(lmax[x],rmax[x]); up(y);up(fa[y]); } } void del(int k,int tot) { int x=split(k,tot),y=fa[x]; recycle(x); son[y][0]=0; up(y);up(fa[y]); } void build(int l,int r,int f) { int mid=(l+r)>>1,now=id[mid],pre=id[f]; if(l==r) { maxans[now]=sum[now]=a[l]; col[now]=rev[now]=0; lmax[now]=rmax[now]=max(0,a[l]); siz[now]=1; } if(l<mid)build(l,mid-1,mid); if(r>mid)build(mid+1,r,mid); v[now]=a[mid];fa[now]=pre; up(now);son[pre][mid>=f]=now; } void insert(int k,int tot) { rep(i,1,tot)scanf("%d",&a[i]); rep(i,1,tot) { if(!q.empty())id[i]=q.front(),q.pop(); else id[i]=++ncnt; } build(1,tot,0); int z=id[(1+tot)>>1]; int x=find1(root,k+1),y=find1(root,k+2); splay(x);splay(y,x); fa[z]=y;son[y][0]=z; up(y);up(x); } int main() { scanf("%d%d",&n,&m); a[1]=a[n+2]=maxans[0]=-inf; rep(i,1,n)scanf("%d",&a[i+1]); rep(i,1,n+2)id[i]=i; build(1,n+2,0); root=(3+n)>>1;ncnt=n+2; int k,tot,val; char ch[10]; int jjj=0; while(m--) { scanf("%s",ch); if(ch[0]!='M'||ch[2]!='X')scanf("%d%d",&k,&tot); if(ch[0]=='I')insert(k,tot); if(ch[0]=='D')del(k,tot); if(ch[0]=='M') { if(ch[2]=='X')printf("%d ",maxans[root]); else scanf("%d",&val),upsum(k,tot,val); } if(ch[0]=='R')rever(k,tot); if(ch[0]=='G')printf("%d ",qsum(k,tot)); } return 0; }