记录编号	371945	评测结果	AAAAAAAAAA
题目名称	地震	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	3.721 s
提交时间	2017-02-17 13:32:12	内存使用	38.44 MiB

#include<cstdio>
typedef long long ll;
const int N=1e6+10;
int read(){
	int x=0;bool sign=1;char ch=getchar();
	while (ch!='-'&&(ch>'9'||ch<'0')) ch=getchar();
	if (ch=='-') sign=0,ch=getchar();
	while (ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
	return sign?x:-x;
}
int n,q,fa[N],son[N][2],s[N],top,root;
ll k[N],tag[N],Max[N];
#define lc son[x][0]
#define rc son[x][1]
void update(int x){
	s[x]=s[lc]+s[rc]+1;
	Max[x]=k[x];
	if (lc&&Max[lc]>Max[x]) Max[x]=Max[lc];
	if (rc&&Max[rc]>Max[x]) Max[x]=Max[rc];
}
void pushdown(int x){
	if (x&&tag[x]){
		if (lc) tag[lc]+=tag[x],k[lc]+=tag[x],Max[lc]+=tag[x];
		if (rc) tag[rc]+=tag[x],k[rc]+=tag[x],Max[rc]+=tag[x];
		tag[x]=0;
	}
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (y==son[z][0]) son[z][0]=x;else
	if (y==son[z][1]) son[z][1]=x;
	update(y);
	update(x);
}
void splay(int x){
	pushdown(x);
	for (;fa[x];rot(x)){
		int y=fa[x],z=fa[y];
		pushdown(z);pushdown(y);pushdown(x);
		if (!fa[z]||!fa[y]) continue;
		rot((x==son[y][0])==(y==son[z][0])?y:x);
	}
	root=x;
}
void find(int R){
	int x=root;
	while (1){
		int i=s[lc]+1;
		if (i==R) break;
		if (R>i) R-=i,x=rc;else x=lc;
	}
	splay(x);
}
int build(int l,int r,int Fa){
	if (l>r) return 0;
	int x=(l+r)>>1;
	lc=build(l,x-1,x);
	rc=build(x+1,r,x);
	fa[x]=Fa;
	update(x);
	return x;
}
void add(int l,int r,int d){
	find(l);find(r+2);
	int le=son[root][0],th=son[le][1];
	tag[th]+=d;k[th]+=d;Max[th]+=d;
	update(le);
	update(root);
}
void insert(int p,int len){
	find(p+1);find(p+2);
	int le=son[root][0];
	for (int i=1;i<=len;i++) k[++top]=read();
	son[le][1]=build(top-len+1,top,le);
	update(le);
	update(root);
}
void del(int l,int r){
	find(l);find(r+2);
	int le=son[root][0];
	son[le][1]=0;
	update(le);
	update(root);
}
void query(int l,int r){
	find(l);find(r+2);
	int le=son[root][0],th=son[le][1];
	printf("%lld\n",Max[th]);
}
int main()
{
	freopen("equake.in","r",stdin);
	freopen("equake.out","w",stdout);
	n=read();q=read();
	for (int i=1;i<=n;i++) k[i+1]=read();
	root=build(1,top=n+2,0);
	char ch[10];int a,b;
	while (q--){
		scanf("%s",ch);
		a=read();b=read();
		if (ch[0]=='R') add(a,b,read());
		if (ch[0]=='I') insert(a,b);
		if (ch[0]=='M') del(a,b);
		if (ch[0]=='Q') query(a,b);
	}
	return 0;
}