https://www.luogu.com.cn/record/99504865

#include<bits/stdc++.h>
using namespace std;
int n,m;
constexpr int lhz=-1145141919;
struct dtp{
	int sum,lmax,rmax,themax;
	dtp(int b,int c,int d,int e):sum(b),lmax(c),rmax(d),themax(e){}
	dtp(int v):sum(v),lmax(v),rmax(v),themax(v){}
	dtp():sum(lhz),lmax(lhz),rmax(lhz),themax(lhz){}
	dtp operator+(const dtp&o)const{
		if(o.sum==lhz)return *this;
		if(sum==lhz)return o;
		return{sum+o.sum,max(lmax,sum+o.lmax),max(o.rmax,rmax+o.sum),max({themax,o.themax,rmax+o.lmax})};
	}
};
mt19937 myrand(time(0));
struct fhqtreap{
	dtp data[500010];
	int val[500010],ls[500010],rs[500010],siz[500010],ftag[500010],atag[500010],rt,stk[500010],tp;
	unsigned int rdval[500010];
	fhqtreap(){for(tp=1;tp<=500000;tp++)stk[tp]=tp;tp--;}
	int node(int x){int p=stk[tp--];data[p]=dtp(x);ls[p]=rs[p]=ftag[p]=0,atag[p]=lhz;val[p]=x;siz[p]=1;rdval[p]=myrand();return p;}
	void free(int id){stk[++tp]=id;}
	void push_up(int p){siz[p]=siz[ls[p]]+siz[rs[p]]+1;data[p]=data[ls[p]]+dtp(val[p])+data[rs[p]];}
	void flnode(int p){ftag[p]^=1;swap(ls[p],rs[p]);}
	void asnode(int p,int v){atag[p]=v;if(v>=0)data[p]=dtp(v*siz[p],v*siz[p],v*siz[p],v*siz[p]);else data[p]=dtp(v*siz[p],v,v,v);}
	void push_down(int p){
		if(ftag[p])flnode(ls[p]),flnode(rs[p]),ftag[p]=0;
		if(atag[p]!=lhz)asnode(ls[p],atag[p]),asnode(rs[p],atag[p]),atag[p]=lhz;
	}
	pair<int,int>split(int p,int k){
		if(!p)return{0,0};
		push_down(p);
		if(k<=siz[ls[p]]){
			auto tmp=split(ls[p],k);
			ls[p]=tmp.second;push_up(p);
			return{tmp.first,p};
		}
		else{
			auto tmp=split(rs[p],k-siz[ls[p]]-1);
			rs[p]=tmp.first;push_up(p);
			return{p,tmp.second};
		}
	}
	int merge(int x,int y){
		if(!x||!y)return x|y;
		push_down(x);push_down(y);
		if(rdval[x]>rdval[y])return rs[x]=merge(rs[x],y),push_up(x),x;
		else return ls[y]=merge(x,ls[y]),push_up(y),y;
	}
	inline auto splitout(int l,int r){auto tmp1=split(rt,r),tmp2=split(tmp1.first,l-1);return make_tuple(tmp2.first,tmp2.second,tmp1.second);}
	inline int merge(int x,int y,int z){return merge(merge(x,y),z);}
	int build(vector<int>&a,int l,int r){
		if(l>r)return 0;
		int mid=(l+r)/2,p=node(a[mid]);
		ls[p]=build(a,l,mid-1);
		rs[p]=build(a,mid+1,r);
		push_up(p);
		return p;
	}
	void ins(int pos,vector<int>&a){
		auto tmp=split(rt,pos);
		int p=build(a,0,a.size()-1);
		rt=merge(tmp.first,p,tmp.second);
	}
	void delt(int p){
		if(!p)return;
		delt(ls[p]),delt(rs[p]);
		free(p);
	}
	void del(int l,int r){
		int a,b,c;tie(a,b,c)=splitout(l,r);
		rt=merge(a,c);
		delt(b);
	}
	void assign(int l,int r,int v){
		int a,b,c;tie(a,b,c)=splitout(l,r);
		asnode(b,v);
		rt=merge(a,b,c);
	}
	void flip(int l,int r){
		int a,b,c;tie(a,b,c)=splitout(l,r);
		flnode(b);
		rt=merge(a,b,c);
	}
	int qsum(int l,int r){
		int a,b,c,v;tie(a,b,c)=splitout(l,r);v=data[b].sum;
		rt=merge(a,b,c);
		return v;
	}
}a;
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	vector<int>e(n);
	for(int i=0;i<n;i++)scanf("%d",&e[i]);
	a.rt=a.build(e,0,e.size()-1);
	char str[20];int pos,tot,c;
	while(m--){
		scanf("%s",str);
		if(str[0]=='I'){scanf("%d%d",&pos,&tot);vector<int>tmp(tot);for(int i=0;i<tot;i++)scanf("%d",&tmp[i]);a.ins(pos,tmp);}
		else if(str[0]=='D'){scanf("%d%d",&pos,&tot);a.del(pos,pos+tot-1);}
		else if(str[2]=='K'){scanf("%d%d%d",&pos,&tot,&c);a.assign(pos,pos+tot-1,c);}
		else if(str[0]=='R'){scanf("%d%d",&pos,&tot);a.flip(pos,pos+tot-1);}
		else if(str[0]=='G'){scanf("%d%d",&pos,&tot);printf("%d\n",a.qsum(pos,pos+tot-1));}
		else printf("%d\n",a.data[a.rt].themax);
	}
	return 0;
}