[cogs347]地震

COGS：地震（平衡樹）

COGS上一道題。。。文件名是equake
還是又打了一遍板子。。。
加個lazy標記就行了。。。
注意查詢時先下傳標記（lazy）

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define Fname "equake"
using namespace std;
#define rep(a,b,c) for(rg int a=b;a<=c;a++)
#define drep(a,b,c) for(rg int a=b;a>=c;a--)
#define erep(a,b) for(rg int a=fir[b];a;a=nxt[a])
#define il inline
#define rg register
#define vd void
#define pr pair<point,point>
#define mp make_pair
typedef long long ll;
il int gi(){rg int x=0,f=1;rg char ch=getchar();while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
int seed=233333333;
il int Rand(){return seed=seed*48271ll%2147483647;}
typedef struct node* point;
point null;
struct node{int data,size,rand,maxx,lazy;point ls,rs;node(int dat){data=maxx=dat,lazy=0,size=1,rand=Rand(),ls=rs=null;}il vd down(){if(this==null)return;data+=lazy,maxx+=lazy,ls->lazy+=lazy,rs->lazy+=lazy,lazy=0;}il vd reset(){ls->down(),rs->down();size=ls->size+rs->size+1;maxx=max(max(ls->maxx,rs->maxx),data);}
};
point root;
il point build(int n){point stack[n+2],last;int top=0;rep(i,1,n){point now=new node(gi());last=null;while(top&&stack[top]->rand>now->rand)last=stack[top],stack[top--]->reset();if(top)stack[top]->rs=now;now->ls=last,stack[++top]=now;}while(top)stack[top--]->reset();return stack[1];
}
il point merge(point a,point b){if(a==null)return b;if(b==null)return a;if(a->rand<b->rand){a->down(),a->rs=merge(a->rs,b),a->reset();return a;}else{b->down(),b->ls=merge(a,b->ls),b->reset();return b;}
}
il pr split(point now,int num){if(now==null)return mp(null,null);now->down();point ls=now->ls,rs=now->rs;if(ls->size==num){now->ls=null,now->reset();return mp(ls,now);}if(ls->size+1==num){now->rs=null,now->reset();return mp(now,rs);}if(ls->size>num){pr T=split(ls,num);now->ls=T.second,now->reset();return mp(T.first,now);}else{pr T=split(rs,num-ls->size-1);now->rs=T.first,now->reset();return mp(now,T.second);}
}
il vd del(point now){if(now!=null)del(now->ls),del(now->rs),delete now;}
int main(){freopen(Fname".in","r",stdin);freopen(Fname".out","w",stdout);int a,b,n=gi(),m=gi();char opt;null=new node(-2e9);null->size=0;root=build(n);while(m--){opt=getchar();while(opt<'A'||opt>'Z')opt=getchar();if(opt=='I'){pr T=split(root,gi());root=merge(T.first,merge(build(gi()),T.second));}else{a=gi(),b=gi();pr T=split(root,a-1),TT=split(T.second,b-a+1);if(opt=='M'){root=merge(T.first,TT.second),del(TT.first);continue;}TT.first->down();if(opt=='R')TT.first->lazy=gi();else printf("%d\n",TT.first->maxx);root=merge(T.first,merge(TT.first,TT.second));}}del(root),delete null;return 0;
}