fhq悬关求助

#include <bits/stdc++.h>
using namespace std;
const int MAXN=4e6+10;
mt19937 myrand(time(0));
struct node{
	int val;
	unsigned pri;
	int ls,rs;
	int size,sum;
	int lt3,lt4;
	int msl,ms,msr;
}nd[MAXN];
int root,num_node;
int New(int val){
	int i=++num_node;
	nd[i].val=nd[i].sum=val;
	nd[i].pri=myrand();
	nd[i].ls=nd[i].rs=0;
	nd[i].msl=nd[i].msr=val<0?0:val;
	nd[i].ms=val;
	nd[i].lt3=nd[i].lt4=-1e9;
	nd[i].size=1;
	return i;
}
void Update(int rt){
	nd[rt].size=nd[nd[rt].ls].size+1+nd[nd[rt].rs].size;
	nd[rt].msl=max(max(nd[nd[rt].ls].msl,nd[rt].val+nd[nd[rt].ls].sum+nd[nd[rt].rs].msl),0);
	nd[rt].ms=max(max(nd[nd[rt].ls].ms,nd[nd[rt].rs].ms),nd[rt].val+nd[nd[rt].ls].msr+nd[nd[rt].rs].msl);
	nd[rt].msr=max(max(nd[nd[rt].rs].msr,nd[nd[rt].ls].msr+nd[nd[rt].rs].sum+nd[rt].val),0);
	nd[rt].sum=nd[nd[rt].ls].sum+nd[nd[rt].rs].sum+nd[rt].val;
}
void Down(int rt){
	if(nd[rt].lt3!=-1e9){
		int k=nd[rt].lt3,l=nd[rt].ls,r=nd[rt].rs;
		if(l){
		    nd[l].val=k;
		    nd[l].msl=nd[l].msr=k<0?0:k*nd[l].size;
		    nd[l].ms=k<0?k:k*nd[l].size;
		    nd[l].sum=k*nd[l].size;nd[l].lt3=k;
		}if(r){
		    nd[r].val=k;
		    nd[r].msl=nd[r].msr=k<0?0:k*nd[r].size;
		    nd[r].ms=k<0?k:k*nd[r].size;
		    nd[r].sum=k*nd[r].size;
		    nd[r].lt3=k;
		}
		nd[rt].lt3=-1e9;
	}if(nd[rt].lt4!=-1e9){
		int l=nd[rt].ls,r=nd[rt].rs;
		if(l){
		    swap(nd[l].ls,nd[l].rs);
		    swap(nd[l].msl,nd[l].msr);
		    nd[l].lt4=0;
		}
		if(r){
		    swap(nd[r].ls,nd[r].rs);
		    swap(nd[r].msl,nd[r].msr);
		    nd[r].lt4=0; 
		}
		nd[rt].lt4=-1e9;
	}
}
void split_rk(int rt,int rk,int &l,int &r){
	if(rt==0){l=0,r=0;return;}
	Down(rt);
	if(nd[nd[rt].ls].size+1<=rk){
		l=rt;
		split_rk(nd[rt].rs,rk-(nd[nd[rt].ls].size+1),nd[rt].rs,r);
	}else{
		r=rt;split_rk(nd[rt].ls,rk,l,nd[rt].ls);
	}Update(rt);
}
int merge(int l,int r){
	if(l==0)return r;
	if(r==0)return l;
	Down(l);Down(r);
	if(nd[l].pri>=nd[r].pri){
		nd[l].rs=merge(nd[l].rs,r);
		Update(l);return l;
	}else{
		nd[r].ls=merge(l,nd[r].ls);
		Update(r);return r;
	}
}int a[500010];
int gettr(int l,int r){
	if(l>r)return 0;
	int mid=(l+r)/2;
	int rt=New(a[mid]);
	nd[rt].ls=gettr(l,mid-1);
	nd[rt].rs=gettr(mid+1,r);
	Update(rt);
	return rt;
}
void Insert(int pos,int rt){
	int a,b;split_rk(root,pos,a,b);
	root=merge(merge(a,rt),b);
}
void Delete(int pos,int tot){
	int l=pos,r=pos+tot-1;
	int a,b,c;
	split_rk(root,r,b,c);
	split_rk(b,l-1,a,b);
	root=merge(a,c);
}
void Change(int pos,int tot,int k){
	int l=pos,r=pos+tot-1;
	int a,b,c;
	split_rk(root,r,b,c);
	split_rk(b,l-1,a,b);
	nd[b].lt3=k;
	nd[b].val=k;
	nd[b].msl=nd[b].msr=k<0?0:k*nd[b].size;
	nd[b].ms=k<0?k:k*nd[b].size;
	nd[b].sum=k*nd[b].size;
	root=merge(merge(a,b),c);
}
void Reverse(int pos,int tot){
	int l=pos,r=pos+tot-1;
	int a,b,c;
	split_rk(root,r,b,c);
	split_rk(b,l-1,a,b);
	nd[b].lt4=0;
	swap(nd[b].ls,nd[b].rs);
	swap(nd[b].msl,nd[b].msr);
	root=merge(merge(a,b),c);
}
int Getsum(int pos,int tot){
	int l=pos,r=pos+tot-1;
	int a,b,c;
	split_rk(root,r,b,c);
	split_rk(b,l-1,a,b);
	int ans=nd[b].sum;
	root=merge(merge(a,b),c);
	return ans;
}
int Maxsum(){
	return nd[root].ms;
}
void getans(int rt){
	if(rt==0)return;
	Down(rt);
	getans(nd[rt].ls);
	cout<<nd[rt].val<<" ";
	getans(nd[rt].rs);
}
signed main(){
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	int n,m;cin>>n>>m;
	nd[0].ms=-5e8;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}Insert(0,gettr(1,n));
	while(m--){
		string op;cin>>op;
		if(op=="INSERT"){
			int pos,tot;cin>>pos>>tot;
			for(int i=1;i<=tot;i++)cin>>a[i];
			if(tot==0)continue;
			Insert(pos,gettr(1,tot));
		}else if(op=="DELETE"){
			int pos,tot;cin>>pos>>tot;
			if(tot==0)continue;
			Delete(pos,tot);
		}else if(op=="MAKE-SAME"){
			int pos,tot,c;cin>>pos>>tot>>c;
			if(tot==0)continue;
			Change(pos,tot,c);
		}else if(op=="REVERSE"){
			int pos,tot;cin>>pos>>tot;
			if(tot==0)continue;
			Reverse(pos,tot);
		}else if(op=="GET-SUM"){
			int pos,tot;cin>>pos>>tot;
			if(tot==0)continue;
			cout<<Getsum(pos,tot)<<"\n";
		}else{
			cout<<Maxsum()<<"\n";
		}//getans(root);cout<<endl;
	}
	return 0;
}