记录编号	255631	评测结果	AAAAAAAAA
题目名称	数列操作B	最终得分	100
用户昵称	Sky_miner	是否通过	通过
代码语言	C++	运行时间	0.174 s
提交时间	2016-04-28 11:49:31	内存使用	34.63 MiB

#include<cstdio>
using namespace std;
#define l(x) son[x][0]
#define r(x) son[x][1]
inline int cat_max(const int &a,const int &b){
	return a>b ? a:b;
}
const int maxn = 1000000 + 100 ;
int cnt,a,b,c,k,rt,son[maxn][2],fa[maxn],s[maxn],mx[maxn],h[maxn],tag[maxn];
int sta[maxn];
int sum[maxn];
void update(int t){
	if( t ){
		s[t] = 1,mx[t] = h[t] ;
		sum[t] = h[t];
		if( l(t) ){
			mx[t] = cat_max(mx[t],mx[l(t)]);
			s[t] += s[l(t)];
			sum[t] += sum[ l(t) ];
		}
		if( r(t) ){
			mx[t] = cat_max(mx[t],mx[r(t)]);
			s[t] += s[r(t)];
			sum[t] += sum[ r(t) ];
		}
	}
}
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];
			sum[l(t)]+= tag[t];
		}
		if( r(t) ){
			tag[r(t)] += tag[t];
			mx[r(t)] += tag[t];
			h[r(t)] += tag[t];
			sum[r(t)] += tag[t];
		}
	}
	tag[t] = 0;
}
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)] = fa[r(mid)] = mid ;
	update(mid);
	return mid;
}
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);
}
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( !fa[p] ) 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);
	}
}
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));
}
void add(){
	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;
	sum[l(r(rt))] += c;
	update(r(rt)),update(rt);
}
void Quer(){
	a = find(a,rt),b = find(b+2,rt);
	splay(rt = b),splay(rt = a);
	printf("%d\n",mx[ l(r(rt)) ]);
}
void Insert(){
	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);
}
void Delete(){
	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);
}
void Sum(){
	a = find(a,rt),b = find(b+2,rt);
	splay(rt = b),splay(rt = a);
	printf("%d\n",sum[ l(r(rt)) ]);
}
void A(){
	char op[2];
	scanf("%s",op);
	if( *op == 'R' ){
		scanf("%d%d%d",&a,&b,&c);
		add();
	}else if( *op == 'Q' ){
		scanf("%d%d",&a,&b);
		Quer();
	}else if( *op == 'I' ){
		scanf("%d%d",&a,&k);
		for(int i=1;i<=k;i++) scanf("%d",&h[cnt+i]);
		Insert();
	}else if( *op == 'M'){
		scanf("%d%d",&a,&b);
		Delete();
	}else if( *op == 'S' ){
		scanf("%d%d",&a,&b);
		Sum();
	}	
}
void my(){
	char op[10];
	scanf("%s",op);
	if( op[0] == 'Q' ){
		scanf("%d",&a);
		b = a;
		Sum();
	}else if( op[0] == 'A' ){
		scanf("%d%d%d",&a,&b,&c);
		add();
	}  
}
int main(){	
	freopen("shulieb.in","r",stdin);
	freopen("shulieb.out","w",stdout);
	int n,q;scanf("%d",&n),cnt = n+2;
	for(int i=1;i<=n;i++) scanf("%d",&h[i+1]);
	scanf("%d",&q);
	for(rt = build(1,cnt);q--;){
		my();
	}
}