记录编号	291353	评测结果	WWWWWWWWW
题目名称	数列操作B	最终得分	0
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	0.172 s
提交时间	2016-08-07 14:53:19	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node{//Splay Tree
	int data,size,lazy;
	node *lch,*rch,*prt;
	node(int d=0):data(d),size(1),lazy(0),lch(NULL),rch(NULL),prt(NULL){}
	void refresh(){
		size=1;
		if(lch)size+=lch->size;
		if(rch)size+=rch->size;
	}
	void pushdown(){
		if(!lazy)return;
		if(lch){
			lch->lazy=lazy;
			lch->data+=lazy;
		}
		if(rch){
			rch->lazy=lazy;
			rch->data+=lazy;
		}
		lazy=0;
	}
}*root=NULL;
void addend(int);
void add(int,int,int);
node *kth(int,node* =root);
void splay(node*,node* =NULL);
void lrot(node*);
void rrot(node*);
int n,m,x,y,z;
char c[10];
node *r;
int main(){
#define MINE
#ifdef MINE
	freopen("shulieb.in","r",stdin);
	freopen("shulieb.out","w",stdout);
#endif
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&x);
		addend(x);
	}
	scanf("%d",&m);
	while(m--){
		scanf("%s",c);
		if(!strcmp(c,"ADD")){
			scanf("%d%d%d",&x,&y,&z);
			add(x,y,z);
		}
		else if(!strcmp(c,"QUERY")){
			scanf("%d",&x);
			r=kth(x);
			splay(r);
			printf("%d\n",r->data);
		}
	}
	return 0;
}
void addend(int x){
	if(!root){
		root=new node(x);
		return;
	}
	node *rt=root;
	while(rt->rch)rt=rt->rch;
	rt->rch=new node(x);
	rt->rch->prt=rt;
	splay(rt->rch);
}
void add(int l,int r,int x){
	if(l==1&&r==n){
		root->lazy+=x;
		root->data+=x;
	}
	else if(l==1&&r!=n){
		splay(kth(r+1));
		root->lch->lazy+=x;
		root->lch->data+=x;
	}
	else if(l!=1&&r==n){
		splay(kth(l-1));
		root->rch->lazy+=x;
		root->rch->data+=x;
	}
	else{
		splay(kth(l-1));
		splay(kth(r+1),root);
		root->rch->lch->lazy+=x;
		root->rch->lch->data+=x;
	}
}
node *kth(int k,node *rt){
	while(rt){
		rt->pushdown();
		if(rt->lch){
			if(k==rt->lch->size+1)return rt;
			else if(k<=rt->lch->size)rt=rt->lch;
			else{
				k-=rt->lch->size+1;
				rt=rt->rch;
			}
		}
		else{
			if(k==1)return rt;
			else{
				k--;
				rt=rt->rch;
			}
		}
	}
	return NULL;
}
void splay(node *x,node *tar){
	for(node *rt=x->prt;rt!=tar;rt=x->prt){
		rt->refresh();
		if(rt->prt==tar){
			if(x==rt->lch)rrot(rt);
			else lrot(rt);
			break;
		}
		else{
			if(rt==rt->prt->lch){
				if(x==rt->lch){
					rrot(rt->prt);
					rrot(rt);
				}
				else{
					lrot(rt);
					rrot(x->prt);
				}
			}
			else{
				if(x==rt->rch){
					lrot(rt->prt);
					lrot(rt);
				}
				else{
					rrot(rt);
					lrot(x->prt);
				}
			}
		}
	}
}
void lrot(node *x){
	if(!x)return;
	node *y=x->rch;
	if(!y)return;
	x->pushdown();
	y->pushdown();
	y->prt=x->prt;
	if(x->prt){
		if(x==x->prt->lch)x->prt->lch=y;
		else x->prt->rch=y;
	}
	else root=y;
	x->rch=y->lch;
	if(y->lch)y->lch->prt=x;
	x->prt=y;
	y->lch=x;
	x->refresh();
	y->refresh();
}
void rrot(node *x){
	if(!x)return;
	node *y=x->lch;
	if(!y)return;
	x->pushdown();
	y->pushdown();
	y->prt=x->prt;
	if(x->prt){
		if(x==x->prt->lch)x->prt->lch=y;
		else x->prt->rch=y;
	}
	else root=y;
	x->lch=y->rch;
	if(y->rch)y->rch->prt=x;
	x->prt=y;
	y->rch=x;
	x->refresh();
	y->refresh();
}