记录编号	457245	评测结果	AAAAAAAAAA
题目名称	地震	最终得分	100
用户昵称	Hzoi_Mafia	是否通过	通过
代码语言	C++	运行时间	1.830 s
提交时间	2017-10-07 10:48:45	内存使用	1.24 MiB

#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
using namespace std;
inline int read(){
	int sum(0),f(1);
	char ch(getchar());
	for(;ch<'0'||ch>'9';ch=getchar())
		if(ch=='-')
			f=-1;
	for(;ch>='0'&&ch<='9';sum=sum*10+(ch^48),ch=getchar());
	return sum*f;
}
#define get_size(x) (x?x->size:0)
#define get_mx(x) (x?x->mx:-0x7fffffff)
struct node{
	node *lch,*rch;
	int key,size,mx,lazy,fix;
	node(int x=0):lch(NULL),rch(NULL),size(1),key(x),mx(x),lazy(0),fix(rand()){}
	inline void add(int x){
		this->key+=x;
		this->mx+=x;
		this->lazy+=x;
	}
	inline void pushup(){
		this->size=get_size(this->lch)+get_size(this->rch)+1;
		this->mx=max(this->key,max(get_mx(this->lch),get_mx(this->rch)));
	}
	inline void pushdown(){
		if(this->lazy){
			if(this->lch)
				this->lch->add(this->lazy);
			if(this->rch)
				this->rch->add(this->lazy);
			this->lazy=0;
		}
	}
}*root;
typedef pair<node*,node*> pii;
int n,m;
int a[100005];
char op[2];
inline pii split(node *x,int k){
	if(!x)
		return pii(NULL,NULL);
	x->pushdown();
	pii y;
	if(get_size(x->lch)>=k){
		y=split(x->lch,k);
		x->lch=y.second;
		x->pushup();
		y.second=x;
	}
	else{
		y=split(x->rch,k-get_size(x->lch)-1);
		x->rch=y.first;
		x->pushup();
		y.first=x;
	}
	return y;
}
inline node* merge(node *x,node *y){
	if(!x)return y;
	if(!y)return x;
	if(x->fix<y->fix){
		x->pushdown();
		x->rch=merge(x->rch,y);
		x->pushup();
		return x;
	}
	else{
		y->pushdown();
		y->lch=merge(x,y->lch);
		y->pushup();
		return y;
	}
}
inline void build(node *&x,int l,int r){
	if(l>r)return;
	int mid((l+r)>>1);
	x=new node(a[mid]);
	build(x->lch,l,mid-1);
	build(x->rch,mid+1,r);
	x->pushup();
}
inline void change(int l,int r,int v){
	pii tp1(split(root,l-1)),tp2(split(tp1.second,r-l+1));
	tp2.first->add(v);
	tp1.second=merge(tp2.first,tp2.second);
	root=merge(tp1.first,tp1.second);
}
inline void insert(int pos,int k){
	for(int i=1;i<=k;++i)
		a[i]=read();
	node *tmp;
	build(tmp,1,k);
	pii tp1(split(root,pos));
	root=merge(tp1.first,merge(tmp,tp1.second));
}
inline void remove(int l,int r){
	pii tp1(split(root,l-1)),tp2(split(tp1.second,r-l+1));
	root=merge(tp1.first,tp2.second);
}
inline int query(int l,int r){
	pii tp1(split(root,l-1)),tp2(split(tp1.second,r-l+1));
	int ret(tp2.first->mx);
	tp1.second=merge(tp2.first,tp2.second);
	root=merge(tp1.first,tp1.second);
	return ret;
}
inline int gg(){
	freopen("equake.in","r",stdin);
	freopen("equake.out","w",stdout);
	srand(time(NULL));
	n=read(),m=read();
	for(int i=1;i<=n;++i)
		a[i]=read();
	build(root,1,n);
	while(m--){
		scanf("%s",op);
		if(op[0]=='R'){
			int x(read()),y(read()),z(read());
			change(x,y,z);
		}
		if(op[0]=='I'){
			int pos(read()),k(read());
			insert(pos,k);
		}
		if(op[0]=='M'){
			int x(read()),y(read());
			remove(x,y);
		}
		if(op[0]=='Q'){
			int x(read()),y(read());
			printf("%d\n",query(x,y));
		}
	}
	return 0;
}
int K(gg());
int main(){;}