记录编号	578327	评测结果	AAAAAAAAAA
题目名称	[AHOI 2006] 可可的文本编辑器	最终得分	100
用户昵称	ムラサメ	是否通过	通过
代码语言	C++	运行时间	0.172 s
提交时间	2023-03-07 19:38:45	内存使用	20.60 MiB

#include <iostream>
#include <cstdio>
#include <cstring>

#define Maxn 2000010

using namespace std;

struct node{
	node *ch[2];
	char v;
	int sum,rev;
	node* init(char x);
	int cmp(int x){
		if(x==ch[0]->sum+1) return -1;
		return x>(ch[0]->sum+1);
	}
	void set();
	void update();
	void pushdown();
}Null,spT[Maxn],*root;

node* node::init(char x){
	v=x; sum=1; ch[0]=ch[1]=&Null;
	rev=0;
	return this;
}

void qread(int &x){
	static char ch;
	while(!isdigit(ch=getchar()));
	x=ch-'0';
	while(isdigit(ch=getchar()))
		x=(x<<1)+(x<<3)+ch-'0';
}

void node::update(){
	if(this==&Null)
		return;
	sum=ch[0]->sum+ch[1]->sum+1;
}

void node::pushdown(){
	if(this==&Null||!rev)
		return;
	swap(ch[0],ch[1]);
	if(ch[0]!=&Null)
		ch[0]->rev^=rev;
	if(ch[1]!=&Null)
		ch[1]->rev^=rev;
	rev=0;
}

void rot(node* &o,int k){
	o->pushdown();
	node* tmp=o->ch[k];
	o->ch[k]->pushdown();
	o->ch[k]=tmp->ch[k^1]; tmp->ch[k^1]->pushdown();
	tmp->ch[k^1]=o; o->update();
	o=tmp; o->update();
}

void splay(node* &o,int k){
	int t1=o->cmp(k); o->pushdown();
	if(t1==-1) return;
	if(t1) k-=o->ch[0]->sum+1;
	o->ch[t1]->pushdown();
	int t2=o->ch[t1]->cmp(k);
	if(~t2){
		o->ch[t1]->ch[t2]->pushdown();
		if(t2) k-=o->ch[t1]->ch[0]->sum+1;
		splay(o->ch[t1]->ch[t2],k);
		if(t1==t2) rot(o,t1);
		else rot(o->ch[t1],t2);
	}
	rot(o,t1);
}

int n,pos=1,tot=0;
char c[Maxn];

node* build(char src[],int l,int r){
	if(l==r) return spT[++tot].init(src[l]);
	int mid=(l+r)>>1;
	node* tmp=spT[++tot].init(src[mid]);
	if(l<=mid-1) tmp->ch[0]=build(src,l,mid-1);
	if(mid+1<=r) tmp->ch[1]=build(src,mid+1,r);
	tmp->update();
	return tmp;
}

void insert(){
	static int len;
	qread(len);
	for(int i=0;i<len;i++){
		do c[i]=getchar();
		while(c[i]<32||c[i]>126);
	}
	c[len]='\0';
	splay(root,pos);
	splay(root->ch[1],1);
	root->pushdown();
	root->ch[1]->pushdown();
	root->ch[1]->ch[0]=build(c,0,len-1);
	root->ch[1]->update();
	root->update();
}

void remove(){
	int len;
	qread(len);
	splay(root,pos);
	splay(root->ch[1],min(len+1,root->ch[1]->sum));
	root->ch[1]->ch[0]=&Null;
}

void reverse(){
	int len;
	qread(len);
	splay(root,pos);
	splay(root->ch[1],len+1);
	root->pushdown();
	root->ch[1]->pushdown();
	node* tmp=root->ch[1]->ch[0];
	tmp->rev^=1;
	tmp->pushdown();
}

void print(){
	root->pushdown();
	splay(root,pos);
	splay(root->ch[1],2);
	root->ch[1]->pushdown();
	putchar(root->ch[1]->ch[0]->v);
	putchar('\n');
}

int main(){
	freopen("editor.in","r",stdin);
	freopen("editor.out","w",stdout);
	qread(n);
	c[0]=c[1]=9;
	root=build(c,0,1);
	char tp,ch;
	for(int i=1,x;i<=n;i++){
		while(!isalpha(ch=getchar()));
		tp=ch;
		while(isalpha(ch=getchar()));
		switch(tp){
			case 'I': insert(); break;
			case 'D': remove(); break;
			case 'M':
				qread(x);
				pos=x+1; break;
			case 'P': pos--; break;
			case 'N': pos++; break;
			case 'R': reverse(); break;
			case 'G': print(); break;
		}
	}
	return 0;
}