记录编号	431471	评测结果	AAAAAAAAAA
题目名称	地震	最终得分	100
用户昵称	Anonymity	是否通过	通过
代码语言	C++	运行时间	2.013 s
提交时间	2017-07-31 20:16:47	内存使用	0.32 MiB

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#define lch ch[0]
#define rch ch[1]
#define kch ch[k]
#define xch ch[k^1]
using namespace std;
inline int read()
{	char c=getchar();int x=0,y=1;
	while(c<'0'||c>'9'){if(c=='-') y=-1;c=getchar();}
	while(c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*y;
}
int inf=0x7fffffff,n,q;
class splay
{	private:
		struct node
		{	int k,s,h,lazy;
			node* pt,*ch[2];
			node(const int& key)
			{	this->k=key;this->s=1;this->lazy=0;
				this->lch=NULL;this->rch=NULL;
			}
			inline int sz(){return this?this->s:0;}
			inline int key(){return this?this->k:0;}
			inline int qh(){return this?this->h:-inf;}
			~node()
			{	if(this->lch) delete this->lch;
				if(this->rch) delete this->rch; 
			}
			inline void mt()
			{	if(this) this->s=this->lch->sz()+this->rch->sz()+1;
				if(this) this->h=std::max(this->k,max(this->lch->qh(),this->rch->qh()));
			}
			inline void dn()
			{	if(this&&this->lazy)
				{	if(lch) lch->lazy+=lazy,lch->k+=lazy,lch->h+=lazy;
					if(rch) rch->lazy+=lazy,rch->k+=lazy,rch->h+=lazy;
					lazy=0;
				}
			}
			inline void Ad(int key){if(this){this->lazy+=key;this->k+=key;this->h+=key;}}
			inline int pos(){return this==this->pt->lch;}
		}*root;
		void rotate(node* rt,int k)
		{	node* tmp=rt->xch;
			rt->dn();tmp->dn();
			tmp->pt=rt->pt;
			if(!rt->pt) this->root=tmp;
			else if(rt->pt->lch==rt) rt->pt->lch=tmp;
			else rt->pt->rch=tmp;
			rt->xch=tmp->kch;
			if(tmp->kch) tmp->kch->pt=rt;
			tmp->kch=rt;rt->pt=tmp;
			rt->mt();tmp->mt();
		}
		void sp(node* rt,node* prt=NULL)
		{	while(rt->pt!=prt)
			{	int k=rt->pt->lch==rt;
				if(rt->pt->pt==prt) rotate(rt->pt,k);
				else
				{	int d=rt->pt->pt->lch==rt->pt;
					rotate(k==d?rt->pt->pt:rt->pt,k);
					rotate(rt->pt,d);
				}
			}
		}
		node* build(const std::vector<int>& v,int l,int r)
		{	if(l>r) return NULL;
			int mid=(l+r)>>1;node* tmp=new node(v[mid]);
			tmp->lch=build(v,l,mid-1);tmp->rch=build(v,mid+1,r);
			if(tmp->lch) tmp->lch->pt=tmp; if(tmp->rch) tmp->rch->pt=tmp;
			tmp->mt();
			return tmp;
		}
	public:
		~splay(){delete this->root;}
		splay(const std::vector<int>& v){this->root=build(v,0,v.size()-1);}
		splay(){this->root=new node(-inf);this->root->rch=new node(-inf);this->root->rch->pt=this->root;}
		node* kth(int x)
		{	++x;
			node* now=this->root;
			while(now!=NULL)
			{	now->dn();
				int k=now->lch->sz()+1;
				if(x<k) now=now->lch;
				else if(x==k) return now;
				else x-=k,now=now->rch;
			}
			return NULL;
		}
		void add(int x,int y,int z)
		{	node* tmp=this->kth(y+1),*tmp2=this->kth(x-1);
			this->sp(tmp2);this->sp(tmp,this->root);
			this->root->rch->lch->Ad(z);
			this->root->rch->mt();this->root->mt();
		}
		void del(int x,int y)
		{	node* tmp=this->kth(y+1),*tmp2=this->kth(x-1);
			this->sp(tmp2);this->sp(tmp,this->root);
			delete this->root->rch->lch;
			this->root->rch->lch=NULL;
			this->root->rch->mt();this->root->mt();
		}
		int hmax(int x,int y)
		{	node* tmp=this->kth(y+1),*tmp2=this->kth(x-1);
			this->sp(tmp2);this->sp(tmp,this->root);
			return this->root->rch->lch->h;
		}
		void insert(int x,splay* data)
		{	this->sp(this->kth(x));this->sp(this->kth(x+1),this->root);
			node* tmp=data->root;data->root=NULL;
			this->root->rch->lch=tmp;tmp->pt=this->root->rch;
			this->root->rch->mt();this->root->mt();
		}
};
int main()
{	freopen("equake.in","r",stdin);
	freopen("equake.out","w",stdout);
	n=read();q=read();
	splay* tree=new splay();
	std::vector<int>v;char ord[10];int x,y,z;
	for(int i=1;i<=n;i++) v.push_back(read());
	tree->insert(0,new splay(v));
	for(int i=1;i<=q;i++)
	{	scanf("%s",ord);
		if(ord[0]=='R'){x=read();y=read();z=read();tree->add(x,y,z);}
		if(ord[0]=='I')
		{	v.clear();x=read();y=read();
			while(y--) v.push_back(read());
			tree->insert(x,new splay(v));
		}
		if(ord[0]=='M'){x=read();y=read();tree->del(x,y);}
		if(ord[0]=='Q'){x=read();y=read();printf("%d\n",tree->hmax(x,y));}
	}
	return 0;
}