记录编号	285068	评测结果	AAAAAAAAAA
题目名称	地震	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	3.884 s
提交时间	2016-07-20 17:27:38	内存使用	27.38 MiB

#include<stdio.h>
#include<algorithm>
#define l(x) son[x][0]
#define r(x) son[x][1]
using namespace std;
int cnt,a,b,c,k,rt,son[1000100][2],fa[1000010];
int s[1000100],mx[1000100],h[1000100],tag[1000100];
int sta[100100];
inline void update(int t){
	if(t){
		s[t]=1,mx[t]=h[t];
		if(l(t)){
			mx[t]=max(mx[t],mx[l(t)]);
			s[t]+=s[l(t)];
		}
		if(r(t)){
			mx[t]=max(mx[t],mx[r(t)]);
			s[t]+=s[r(t)];
		}
	}
}
inline void pushdown(int t){
	if(tag[t]){
		if(l(t)){
			tag[l(t)]+=tag[t];
			mx[l(t)]+=tag[t];
			h[l(t)]+=tag[t];
		}
		if(r(t)){
			tag[r(t)]+=tag[t];
			mx[r(t)]+=tag[t];
			h[r(t)]+=tag[t];
		}
		tag[t]=0;
	}
}
inline int build(int l,int r){
	if(l>r)return 0;
	int mid=l+r>>1;
	l(mid)=build(l,mid-1);
	r(mid)=build(mid+1,r);
	fa[l(mid)]=mid,fa[r(mid)]=mid;
	return update(mid),mid;
}
inline void rotate(int x,bool k){
	int y=son[x][k^1];
	son[x][k^1]=son[y][k];
	fa[son[x][k^1]]=x;
	son[y][k]=x;
	if(x==l(fa[x]))l(fa[x])=y;
	else if(x==r(fa[x]))r(fa[x])=y;
	fa[y]=fa[x],fa[x]=y;
	update(x);
}
inline void splay(int p){
	sta[++sta[0]]=p;
	for(int i=p;fa[i];i=fa[i])sta[++sta[0]]=fa[i];
	while(sta[0])pushdown(sta[sta[0]--]);
	for(int x,y;fa[p];){
		x=fa[p],y=fa[x];
		if(!y)rotate(x,l(x)==p);
		else if((l(y)==x)==(l(x)==p)){
			if(l(y)==x)rotate(x,1),rotate(y,1);//右旋
			else rotate(x,0),rotate(y,0);//左旋
		}else rotate(x,l(x)==p),rotate(y,l(y)==p);
	}update(p);
}
inline int find(int x,int p){
	if(s[l(p)]+1==x)return p;
	if(s[l(p)]+1<x)return find(x-s[l(p)]-1,r(p));
	return find(x,l(p));
}
int main(){
	freopen("equake.in","r",stdin);
	freopen("equake.out","w",stdout);
	int n,q;char op[2];scanf("%d%d",&n,&q),cnt=n+2;
	for(int i=1;i<=n;++i)scanf("%d",&h[i+1]);
	for(rt=build(1,cnt);q--;){
		scanf("%s",op);
		if(*op=='R'){//区间加上一个值
			scanf("%d%d%d",&a,&b,&c);
			a=find(a,rt),b=find(b+2,rt);
			splay(rt=b),splay(rt=a);
			tag[l(r(rt))]+=c;
			mx[l(r(rt))]+=c;
			h[l(r(rt))]+=c;
			update(r(rt)),update(rt);
		}else if(*op=='I'){//插入一个区间
			scanf("%d%d",&a,&k);
			for(int i=1;i<=k;++i)
			    scanf("%d",&h[cnt+i]);
			cnt+=k;
			k=build(cnt-k+1,cnt);
			b=find(a+2,rt),a=find(a+1,rt);
			splay(rt=b),splay(rt=a);
			fa[k]=r(rt),l(r(rt))=k;
			update(r(rt)),update(rt);
		}else if(*op=='M'){//删去一个区间
			scanf("%d%d",&a,&b);
			a=find(a,rt),b=find(b+2,rt);
			splay(rt=b),splay(rt=a);
			fa[l(r(rt))]=0,l(r(rt))=0;
			update(r(rt)),update(rt);
		}else{//查询区间最值
			scanf("%d%d",&a,&b);
			a=find(a,rt),b=find(b+2,rt);
			splay(rt=b),splay(rt=a);
			printf("%d\n",mx[l(r(rt))]);
		}
	}
}