萌新球条 fhq 10pts

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10;
const int E=1e9;
int n,m,root;
struct Node{
	int v,w,l,r;
	int siz,sum,lmax,rmax,maxe;
	int tag;
	bool re;
}a[N];
stack<int>ID;
int New(int x) {
	int t=ID.top();
	ID.pop();
	a[t]={x,rand(),0ll,0ll,1ll,x,max(x,0ll),max(x,0ll),x,E,0ll};
	return t;
}

void recycle(int k) {
	if(!k)return;
	recycle(a[k].l);
	ID.push(k);
	recycle(a[k].r);
	return;
}

void pushup(int x) {
	a[x].siz=a[a[x].l].siz+a[a[x].r].siz+1;
	a[x].sum=a[a[x].l].sum+a[a[x].r].sum+a[x].v;
	a[x].lmax=max(a[a[x].l].lmax , a[a[x].l].sum+a[x].v+a[a[x].r].lmax);
	a[x].rmax=max(a[a[x].r].rmax , a[a[x].r].sum+a[x].v+a[a[x].l].rmax);
	a[x].maxe=max(a[a[x].l].rmax+a[x].v+a[a[x].r].lmax , max(a[a[x].l].maxe , a[a[x].r].maxe));
	return;
}

void reverse(int x) {
	if(!x)return;
	a[x].re^=1;
	swap(a[x].lmax,a[x].rmax);
	swap(a[x].l,a[x].r);
	return;
}

void cover(int x,int c) {
	if(!x)return;
	a[x].v=c;
	a[x].sum=a[x].siz*c;
	a[x].lmax=a[x].rmax=max(0ll,a[x].sum);
	a[x].maxe=max(c,a[x].sum);
	a[x].tag=c;
	a[x].re=0;
	return;
}

void pushdown(int x) {
	if(a[x].tag!=E) {
		cover(a[x].l,a[x].tag);
		cover(a[x].r,a[x].tag);
		a[x].tag=E;
	}
	if(a[x].re) {
		reverse(a[x].l);
		reverse(a[x].r);
		a[x].re=0;
	}
	pushup(x);
	return;
}

void split_size(int k,int t,int &x,int &y) {
    if (!k) {
        x=y=0;
        return;
    }
    if(a[a[k].l].siz+1ll<=t) {
    	x=k;
    	split_size(a[k].r,t-a[a[k].l].siz-1ll,a[k].r,y);
		pushup(x);
	}else {
       	y=k;
        split_size(a[k].l,t,x,a[k].l);
        pushup(y);
    }
    return;
}

int merge(int x,int y) {
	if(!x||!y)return x+y;
	if(a[x].w>a[y].w) {
		pushdown(x);
		a[x].r=merge(a[x].r,y);
		pushup(x);
		return x;
	}
	pushdown(y);
	a[y].l=merge(x,a[y].l);
	pushup(y);
	return y;
}

//void print(int x) {
//	if(!x)return;
//	pushdown(x);
//	print(a[x].l);
//	cout<<a[x].v<<" ";
//	print(a[x].r);
//	return;
//}
int x,y,z;
signed main() {
	srand(time(0));
	a[0].maxe=-1e18;
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	for(int i=500000;i>=1;i--)ID.push(i);
	cin>>n>>m;
	for(int i=1;i<=n;i++) {
		cin>>x;
		root=merge(root,New(x));
//		cout<<root<<" "<<a[root].l<<" "<<a[root].r<<endl;
//		print(root);
//		cout<<endl;
	}
	string op;
	int pos,tot,c;
	while(m--) {
		cin>>op;
		x=y=z=0;
		if(op=="INSERT") {
			cin>>pos>>tot;
			split_size(root,pos,x,y);
//			cout<<a[x].siz<<endl;
//			print(x);
//			cout<<endl;
//			cout<<a[y].siz<<endl;
//			print(y);
//			cout<<endl;
			while(tot--) {
				cin>>c;
				x=merge(x,New(c));
			}
			root=merge(x,y);
		}
		if(op=="DELETE") {
			cin>>pos>>tot;
			split_size(root,pos-1ll,x,y);
			split_size(y,tot,z,y);
			root=merge(x,y);
			recycle(z);
		}
		if(op=="MAKE-SAME") {
			cin>>pos>>tot>>c;
			split_size(root,pos-1ll,x,y);
			split_size(y,tot,z,y);
//			cout<<a[z].siz<<endl;
			cover(z,c);
//			print(z);
//			cout<<endl;
			root=merge(merge(x,z),y);
		}
		if(op=="REVERSE") {
			cin>>pos>>tot;
			split_size(root,pos-1ll,x,y);
			split_size(y,tot,z,y);
			reverse(z);
			root=merge(merge(x,z),y);
		}
		if(op=="GET-SUM") {
			cin>>pos>>tot;
			split_size(root,pos-1ll,x,y);
			split_size(y,tot,z,y);
			cout<<a[z].sum<<endl;
			root=merge(merge(x,z),y);
		}
		if(op=="MAX-SUM") {
			cout<<a[root].maxe<<endl;
		}
//		print(root);
//		cout<<endl;
	}
	return 0;
}
/*
struct Node{
	int v,w,s[2];
	int siz,sum,lmax,rmax,maxe;
	int tag;
	bool re;
}a[N];
*/

/*
3 4
1 2 3
INSERT 1 2 4 5
MAKE-SAME 2 3 6
REVERSE 3 3
*/
/*
2 -6 6 -3 -5 2 2 2 -5 7 2
*/