原题

解析

一个一个操作考虑

插入

先将加入序列递归建树，然后类似于平衡树的插入，将根节点插到原树中

删除

将区间提出来删除，类似于平衡树的remove

赋值，翻转

类似于文艺平衡树，提出区间后打标记，然后在find（改变树形态时pushdown）

求和，求最大子段和

提出区间即可，pushup于线段树类似，注意要包含根节点

#include
using namespace std;
#define mid ((l+r)>>1)
#define ls tr[p].ch[0]
#define rs tr[p].ch[1]
const int N=1e6+5,inf=0x3f3f3f3f;
struct node{int val,siz,sum,mx,lx,rx,fa,ch[2];int tag,rev;void clear(){val=siz=sum=mx=lx=rx=fa=ch[0]=ch[1]=tag=rev=0;}
}tr[N];
int id[N],rt,a[N],tot,n,m;
queue q;
void pushup(int p){tr[p].siz=tr[ls].siz+tr[rs].siz+1,tr[p].sum=tr[ls].sum+tr[rs].sum+tr[p].val;tr[p].mx=max(max(tr[ls].mx,tr[rs].mx),tr[ls].rx+tr[rs].lx+tr[p].val);tr[p].lx=max(tr[ls].lx,tr[ls].sum+tr[rs].lx+tr[p].val),tr[p].rx=max(tr[rs].rx,tr[rs].sum+tr[ls].rx+tr[p].val);
}
void add_tag(int p,int v){if(!p) return;tr[p].tag=tr[p].val=v,tr[p].sum=tr[p].siz*tr[p].val;tr[p].lx=tr[p].rx=max(0,tr[p].sum);tr[p].mx=max(tr[p].val,tr[p].sum);
}
void add_rev(int p){if(p) swap(tr[p].lx,tr[p].rx),swap(ls,rs),tr[p].rev^=1;}
void pushdown(int p){if(tr[p].tag!=inf){add_tag(ls,tr[p].tag),add_tag(rs,tr[p].tag);tr[p].tag=inf,tr[p].rev=0;}if(tr[p].rev){add_rev(ls),add_rev(rs);tr[p].rev=0;}
}
bool ist(int x){return tr[tr[x].fa].ch[1]==x;}
void rotate(int x){int y=tr[x].fa,z=tr[y].fa,d=ist(x),d1=ist(y);pushdown(y),pushdown(x);tr[y].ch[d]=tr[x].ch[d^1],tr[tr[x].ch[d^1]].fa=y;tr[x].ch[d^1]=y,tr[y].fa=x;if(z) tr[z].ch[d1]=x;tr[x].fa=z;pushup(y),pushup(x);
}
void splay(int x,int k){while(tr[x].fa!=k){int y=tr[x].fa,z=tr[y].fa;if(z!=k&&z) ist(x)^ist(y)?rotate(x):rotate(y);rotate(x);}if(!k) rt=x;
}
int find(int p,int x){pushdown(p);if(x<=tr[ls].siz) return find(ls,x);else if(x==tr[ls].siz+1) return p;else return find(rs,x-tr[ls].siz-1);
}
void build(int l,int r,int fa){int now=id[mid],pre=id[fa];tr[now].tag=inf;if(l==r){tr[now].val=tr[now].sum=tr[now].mx=a[l];tr[now].lx=tr[now].rx=max(0,a[l]);tr[now].siz=1,tr[now].tag=inf,tr[now].rev=tr[now].ch[0]=tr[now].ch[1]=0;}if(lmid) build(mid+1,r,mid);tr[now].fa=pre,tr[pre].ch[mid>=fa]=now,tr[now].val=a[mid];if(l>a[i];id[i]=create();}build(1,t,0);int q=find(rt,k+1),p=find(rt,k+2),z=id[(t+1)>>1];splay(q,0),splay(p,q);ls=z,tr[z].fa=p;pushup(p),pushup(q);
}
void remove(int k,int t){int q=find(rt,k),p=find(rt,k+t+1);splay(q,0),splay(p,q);del(ls);pushup(p),pushup(q);
}
void update(int k,int t,int c){int q=find(rt,k),p=find(rt,k+t+1);splay(q,0),splay(p,q);add_tag(ls,c);pushup(p),pushup(q);
}
void reverse(int k,int t){int q=find(rt,k),p=find(rt,k+t+1);splay(q,0),splay(p,q);add_rev(ls);pushup(p),pushup(q);
}
int query_sum(int k,int t){int q=find(rt,k),p=find(rt,k+t+1);splay(q,0),splay(p,q);return tr[ls].sum;
}
int main(){cin>>n>>m;tr[0].mx=a[1]=a[n+2]=-inf;for(int i=1;i<=n;i++) cin>>a[i+1];for(int i=1;i<=n+2;i++) id[i]=create();build(1,n+2,0);rt=(n+3)>>1;for(int i=1;i<=m;i++){string s;int pos,t,c;cin>>s;if(s[0]=='M'&&s[2]=='X'){cout<>pos>>t;if(s[0]=='I') insert(pos,t);if(s[0]=='D') remove(pos,t);if(s[0]=='M'&&s[2]=='K'){cin>>c;update(pos,t,c);}if(s[0]=='R') reverse(pos,t);if(s[0]=='G') cout<

启发

平衡树实现区间操作的方法

int p=pre(l-1),q=suf(r)
splay(p,0),splay(q,p)
update(ch[q][0])

​