记录编号	329469	评测结果	AAAAAAAAAAAAAAAAAAAT
题目名称	2385.小F的数列编辑器	最终得分	95
用户昵称	AntiLeaf	是否通过	未通过
代码语言	C++	运行时间	2.651 s
提交时间	2016-10-25 16:09:52	内存使用	0.26 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF (0x3f3f3f3f)
#define siz(x) ((x)?((x)->size):(0))
#define sm(x) ((x)?((x)->sum):(0))
#define pref(x) ((x)?((x)->prefix):(-INF))
using namespace std;
struct node{
	int data,size,sum,prefix;
	node *lc,*rc,*prt;
	node(int d):data(d),size(1),sum(d),prefix(d),lc(NULL),rc(NULL),prt(NULL){}
	void refresh(){
		size=siz(lc)+siz(rc)+1;
		sum=sm(lc)+sm(rc)+data;
		if(!lc)prefix=data+max(pref(rc),0);
		else prefix=max(pref(lc),sm(lc)+data+max(pref(rc),0));
	}
}*root=NULL;
void insert(int,int);
void erase(node*);
int query(int);
node *kth(int);
void splay(node*,node*);
void lrot(node*);
void rrot(node*);
node *findmax(node*);
int n,x,now=0;
char c;
int main(){
#define MINE
#ifdef MINE
	freopen("EXeditor.in","r",stdin);
	freopen("EXeditor.out","w",stdout);
#endif
	scanf("%d",&n);
	while(n--){
		scanf(" %c",&c);
		if(c=='I'){
			scanf("%d",&x);
			insert(x,now++);
		}
		else if(c=='D')erase(kth(now--));
		else if(c=='L'){
			if(now)now--;
		}
		else if(c=='R'){
			if(now<siz(root))now++;
		}
		else{
			scanf("%d",&x);
			printf("%d\n",query(x));
		}
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#else
	fclose(stdin);
	fclose(stdout);
#endif
	return 0;
}
void insert(int x,int k){
	if(!root){
		root=new node(x);
		return;
	}
	if(!k){
		node *y=new node(x);
		y->rc=root;
		if(root)root->prt=y;
		root=y;
		y->refresh();
		return;
	}
	splay(kth(k),NULL);
	node *y=root->rc;
	root->rc=new node(x);
	root->rc->prt=root;
	root->rc->rc=y;
	if(y)y->prt=root->rc;
	root->rc->refresh();
	root->refresh();
}
void erase(node *x){
	splay(x,NULL);
	if(x->lc){
		splay(findmax(x->lc),x);
		x->lc->rc=x->rc;
		x->lc->prt=NULL;
		root=x->lc;
	}
	else root=x->rc;
	if(x->rc)x->rc->prt=x->lc;
	delete x;
	if(root)root->refresh();
}
int query(int k){
	if(k==siz(root))return pref(root);
	splay(kth(k+1),NULL);
	return pref(root->lc);
}
node *kth(int k){
	node *rt=root;
	while(rt){
		if(k==siz(rt->lc)+1)return rt;
		else if(k<=siz(rt->lc))rt=rt->lc;
		else{
			k-=siz(rt->lc)+1;
			rt=rt->rc;
		}
	}
	return NULL;
}
void splay(node *x,node *tar){
	if(!x)return;
	for(node *rt=x->prt;rt!=tar;rt=x->prt){
		if(rt->prt==tar){
			if(x==rt->lc)rrot(rt);
			else lrot(rt);
			break;
		}
		if(rt==rt->prt->lc){
			if(x==rt->lc)rrot(rt);
			else lrot(rt);
			rrot(x->prt);
		}
		else{
			if(x==rt->rc)lrot(rt);
			else rrot(rt);
			lrot(x->prt);
		}
	}
}
void lrot(node *x){
	node *y=x->rc;
	if(x->prt){
		if(x==x->prt->lc)x->prt->lc=y;
		else x->prt->rc=y;
	}
	else root=y;
	y->prt=x->prt;
	x->rc=y->lc;
	if(y->lc)y->lc->prt=x;
	y->lc=x;
	x->prt=y;
	x->refresh();
	y->refresh();
}
void rrot(node *x){
	node *y=x->lc;
	if(x->prt){
		if(x==x->prt->lc)x->prt->lc=y;
		else x->prt->rc=y;
	}
	else root=y;
	y->prt=x->prt;
	x->lc=y->rc;
	if(y->rc)y->rc->prt=x;
	y->rc=x;
	x->prt=y;
	x->refresh();
	y->refresh();
}
node *findmax(node *x){
	if(!x)return NULL;
	while(x->rc)x=x->rc;
	return x;
}