P2042，10pts求条。

#include<cstdio>
#include<stack>
struct node{
	int left,right,value,lazy,size;
	bool reverse,change;
	int sum,head,tail,all;
};
node tree[500005];
std::stack<int> stack;
int top,root,size,action,data[500005];
inline int max(int first,int second){
	if(first>second){
		return first;
	};
	return second;
};
inline void swap(int &first,int &second){
	first^=second^=first^=second;
	return;
};
inline int newnode(int value){
	top=stack.top();
	stack.pop();
	tree[top].left=tree[top].right=0;
	tree[top].reverse=tree[top].change=false;
	tree[top].size=1;
	tree[top].value=tree[top].sum=tree[top].all=value;
	tree[top].head=tree[top].tail=max(0,value);
	return top;
};
inline void pushup(int root){
	if(!root){
		return;
	};
	tree[root].size=tree[tree[root].left].size+tree[tree[root].right].size+1;
	tree[root].sum=tree[tree[root].left].sum+tree[tree[root].right].sum+tree[root].value;
	tree[root].head=max(max(tree[tree[root].left].head,tree[tree[root].left].sum+tree[root].value+tree[tree[root].right].head),0);
	tree[root].tail=max(max(tree[tree[root].right].tail,tree[tree[root].right].sum+tree[root].value+tree[tree[root].left].tail),0);
	tree[root].all=max(tree[root].value,tree[root].value+tree[tree[root].left].tail+tree[tree[root].right].head);
	if(tree[root].left){
		tree[root].all=max(tree[root].all,tree[tree[root].left].all);
	};
	if(tree[root].right){
		tree[root].all=max(tree[root].all,tree[tree[root].right].all);
	};
	return;
};
inline void reverse(int root){
	if(!root){
		return;
	};
	swap(tree[root].left,tree[root].right);
	swap(tree[root].head,tree[root].tail);
	tree[root].reverse^=true;
	return;
};
inline void change(int root,int value){
	tree[root].value=tree[root].lazy=value;
	tree[root].sum=tree[root].size*value;
	tree[root].head=tree[root].tail=max(0,tree[root].sum);
	tree[root].tail=max(value,tree[root].sum);
	tree[root].change=true;
	return;
};
inline void pushdown(int root){
	if(!root){
		return;
	};
	if(tree[root].reverse){
		if(tree[root].left){
			reverse(tree[root].left);
		};
		if(tree[root].right){
			reverse(tree[root].right);
		};
		tree[root].reverse=false;
	};
	if(tree[root].change){
		if(tree[root].left){
			change(tree[root].left,tree[root].lazy);
		};
		if(tree[root].right){
			change(tree[root].right,tree[root].lazy);
		};
		tree[root].lazy=0;
		tree[root].change=false;
	};
	return;
};
inline void erase(int value){
	if(!root){
		return;
	};
	stack.push(value);
	if(tree[value].left){
		erase(tree[value].left);
	};
	if(tree[value].right){
		erase(tree[value].right);
	};
	return;
};
inline void split(int root,int value,int &first,int &second){
	if(!root){
		first=second=0;
		return;
	};
	pushdown(root);
	if(tree[tree[root].left].size<value){
		first=root;
		split(tree[root].right,value-tree[tree[root].left].size-1,tree[first].right,second);
	}else{
		second=root;
		split(tree[root].left,value,first,tree[second].left);
	};
	pushup(root);
	return;
};
inline int merge(int first,int second){
	if(!first||!second){
		return first+second;
	};
	if(90000008%(tree[first].size+tree[second].size)<tree[first].size){
		pushdown(first);
		tree[first].right=merge(tree[first].right,second);
		pushup(first);
		return first;
	};
	pushdown(second);
	tree[second].left=merge(first,tree[second].left);
	pushup(second);
	return second;
};
inline int build(int first,int last){
	if(first==last){
		return newnode(data[first]);
	};
	int middle=first+last>>1;
	return merge(build(first,middle),build(middle+1,last));
};
int main(int argc,char **argv){
	scanf("%d %d",&size,&action);
	for(int iter=1;iter<=500000;++iter){
		stack.push(iter);
	};
	for(int iter=1;iter<=size;++iter){
		scanf("%d",&data[iter]);
	};
	root=merge(root,build(1,size));
	do{
		char str[11];
		scanf("%s",str);
		if(str[0]=='I'){
			int pos,size,first,second;
			scanf("%d %d",&pos,&size);
			split(root,pos,first,second);
			for(int iter=1;iter<=size;++iter){
				scanf("%d",&data[iter]);
			};
			root=merge(merge(first,build(1,size)),second);
//			printf("%d\n",root);
		}else if(str[0]=='D'){
			int pos,size,first,second,third;
			scanf("%d %d",&pos,&size);
			split(root,pos-1,first,second);
			split(second,size,second,third);
			erase(second);
			root=merge(first,third);
//			printf("%d\n",root);
		}else if(str[0]=='M'&&str[2]=='K'){
			int pos,size,value,first,second,third;
			scanf("%d %d %d",&pos,&size,&value);
			split(root,pos-1,first,second);
			split(second,size,second,third);
			change(second,value);
			root=merge(merge(first,second),third);
//			printf("%d\n",root);
		}else if(str[0]=='R'){
			int pos,size,first,second,third;
			scanf("%d %d",&pos,&size);
			split(root,pos-1,first,second);
			split(second,size,second,third);
			reverse(second);
			root=merge(merge(first,second),third);
//			printf("%d\n",root);
		}else if(str[0]=='G'){
			int pos,size,first,second,third;
			scanf("%d %d",&pos,&size);
			split(root,pos-1,first,second);
			split(second,size,second,third);
			printf("%d\n",tree[second].sum);
			root=merge(merge(first,second),third);
//			printf("%d\n",root);
		}else if(str[0]=='M'&&str[2]=='X'){
			printf("%d\n",tree[root].all);
		};
	}while(--action);
	return 0;
};