记录编号	329474	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	小F的数列编辑器	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	2.375 s
提交时间	2016-10-25 16:17:56	内存使用	24.64 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;
namespace mine{
	template<class T>inline void readint(T &__x){
		static int __c;
		static bool __neg;
		__x=0;
		__neg=false;
		do __c=getchar();while(__c==' '||__c=='\n'||__c=='\r'||__c=='\t');
		if(__c=='-'){
			__neg=true;
			__c=getchar();
		}
		for(;__c>='0'&&__c<='9';__c=getchar())__x=__x*10+(__c^48);
		if(__neg)__x=-__x;
	}
	template<class T>inline void putint(T __x){
		static int __a[40],__i,__j;
		static bool __neg;
		__neg=__x<0;
		if(__neg)__x=-__x;
		__i=0;
		do{
			__a[__i++]=__x%(T)10^(T)48;
			__x/=10;
		}while(__x);
		if(__neg)putchar('-');
		for(__j=__i-1;__j^-1;__j--)putchar(__a[__j]);
	}
}
using namespace mine;
struct node{
	int data,size,sum,prefix;
	node *lc,*rc,*prt;
	node(int d=0):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,pl[1000010],*pool[1000010];
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*);
node *newnode(int);
void delnode(node*);
int n,x,now=0,top;
char c;
int main(){
#define MINE
#ifdef MINE
	freopen("EXeditor.in","r",stdin);
	freopen("EXeditor.out","w",stdout);
#endif
	readint(n);
	for(int i=0;i<=n;i++)pool[i]=&pl[i];
	top=n;
	while(n--){
		do c=getchar();while(c^'I'&&c^'D'&&c^'L'&&c^'R'&&c^'Q');
		if(c=='I'){
			readint(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{
			readint(x);
			putint(query(x));
			putchar('\n');
		}
	}
#ifndef MINE
	printf("\n-------------------------DONE-------------------------\n");
	for(;;);
#else
	fclose(stdin);
	fclose(stdout);
#endif
	return 0;
}
void insert(int x,int k){
	if(!root){
		root=newnode(x);
		return;
	}
	if(!k){
		node *y=newnode(x);
		y->rc=root;
		if(root)root->prt=y;
		root=y;
		y->refresh();
		return;
	}
	splay(kth(k),NULL);
	node *y=root->rc;
	root->rc=newnode(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;
	delnode(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;
}
inline node *newnode(int d){
	*pool[top]=node(d);
	return pool[top--];
}
inline void delnode(node *x){
	pool[++top]=x;
}