记录编号	140538	评测结果	AAAAAAAAAA
题目名称	[NOI 2003]文本编辑器	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.797 s
提交时间	2014-11-22 18:11:16	内存使用	42.31 MiB

#include <cstdio>
#include <iostream>
#include <cctype>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <assert.h>
#include <ctime>
using namespace std;
#if defined DEBUG
FILE *in = fopen("test", "r");
//#define out stdout
FILE *out = fopen("editor2003.out", "w");
#else
FILE *in = fopen("editor2003.in", "r");
FILE *out = fopen("editor2003.out", "w");
#endif
inline void getd(int &x){
	char c = fgetc(in);
	bool minus = 0;
	while(!isdigit(c))c = fgetc(in);
	x = c - '0';
	while(isdigit(c = fgetc(in)))x = x * 10 - '0' + c;
	if(minus)x = -x;
}
/*=====================================================*/
const int maxn = (1 << 21) + 3;
struct SPLAY{
	int key, size;
	SPLAY *son[2], *p;
	SPLAY(int k):key(k), size(0){son[0] = son[1] = p = NULL;}
	SPLAY():size(1){}
	void rot(), splay(SPLAY*), next(), prev(), get();
	SPLAY *find(int k){
		assert(k && k <= size);
		if(size == 1)return this;
		if(k <= son[0]->size) return son[0]->find(k);
		if((k -= son[0]->size) == (bool)key) return this;
		return son[1]->find(k - (key>0));
	}
}nil(0), ptr(0), Pool[maxn];
int it = 0;
char buf[maxn];

inline void update(SPLAY *x){x->size = x->son[0]->size + x->son[1]->size + 1;}
inline bool valid(int ch){return ch < 127 && ch > 31;}

inline SPLAY *newT(char *str, int len){
	int mid = len >> 1;
	SPLAY *ans = Pool + it++;
	ans->key = str[mid];
	ans->size = len;
	ans->p = ans->son[0] = ans->son[1] = &nil;
	if(mid) ans->son[0] = newT(str, mid), ans->son[0]->p = ans;
	if(len-mid-1) ans->son[1] = newT(str+mid+1, len-mid-1),
			ans->son[1]->p = ans;
	return ans;
}

void SPLAY::rot(){
	bool lr = (this == p->son[1]);
	bool plr = (p == p->p->son[1]);
	p->son[lr] = son[lr^1], son[lr^1]->p = p, son[lr^1] = p;
	p = p->p, p->son[plr] = this, son[lr^1]->p = this;
	update(son[lr^1]);
}

void SPLAY::splay(SPLAY *x){
	assert(this != &nil && x != &nil);
	while(x->p != this){
		if(x->p->p != this){
			bool lr = (x==x->p->son[1]);
			bool plr = (x->p==x->p->p->son[1]);
			if(lr == plr)
				x->p->rot();
			else x->rot();
		}
		x->rot();
	}
	update(x);
}

void SPLAY::get(){
	assert(this != &nil);
	if(son[0] != &nil) son[0]->get();
	if(key) fputc(key, out);
	if(son[1] != &nil) son[1]->get();
}

SPLAY *merge(SPLAY *a, SPLAY *b){
	if(a == &nil)return b;
	if(b == &nil)return a;
	SPLAY *x = b->find(1);
	b->p->splay(x);
	a->p = x; x->son[0] = a;
	x->size += a->size;
	return x;
}

void split(SPLAY *x, int k, SPLAY* &a, SPLAY* &b){
	assert(x->size >= k);
	if(k == 0){
		a = &nil; b = x;
		return;
	}
	a = x->find(k); x->p->splay(a);
	b = a->son[1]; b->p = &nil;
	a->size -= b->size; a->son[1] = &nil;
}

void SPLAY::next(){
	assert(son[1] != &nil);
	SPLAY *x = son[1]->find(1);
	splay(x);
	x->son[0] = son[0];
	x->size = son[0]->size + 1;
	son[0]->p = x;
	son[0] = x;
	son[1] = x->son[1];
	x->son[1] = &nil;
	son[1]->p = this;
}

void SPLAY::prev(){
	assert(son[0] != &nil);
	SPLAY *x = son[0]->find(son[0]->size);
	splay(x);
	x->son[1] = son[1];
	x->size = son[1]->size + 1;
	son[1]->p = x;
	son[1] = x;
	son[0] = x->son[0];
	x->son[0] = &nil;
	son[0]->p = this;
	
}

inline void Move(){
	int k; getd(k);
	SPLAY *t = merge(ptr.son[0], ptr.son[1]);
	split(t, k, ptr.son[0], ptr.son[1]);
	ptr.son[0]->p = ptr.son[1]->p = &ptr;
}

inline void Insert(){
	int len, i; getd(len);
	for(i = 0;i < len;++i)
		while(!valid(buf[i] = fgetc(in)));
	if(ptr.son[1] == &nil){
		ptr.son[1] = newT(buf, len);
		ptr.son[1]->p = &ptr;
		ptr.size += ptr.son[1]->size;
		return;
	}
	SPLAY *t = ptr.son[1]->find(1);
	ptr.splay(t);
	t->son[0] = newT(buf, len);
	ptr.son[1]->p = &ptr;
	t->son[0]->p = t;
	update(t);
	update(&ptr);
}

inline void Del(){
	int k; getd(k);
	SPLAY *a, *b;
	split(ptr.son[1], k, a, b);
	ptr.son[1] = b;
	b->p = &ptr;
	update(&ptr);
}

inline void Get(){
	int k; getd(k);
	if(ptr.son[1]->size == k)
		ptr.son[1]->get();
	else{
		ptr.splay(ptr.son[1]->find(k+1));
		ptr.son[1]->son[0]->get();
	}
	fputc('\n', out);
}

int main(){
	ptr.p = ptr.son[0] = ptr.son[1] = &nil;
	int T, ord;
	getd(T);
	while(T--){
		while(!isalpha(ord = fgetc(in)));
		while(isalpha(fgetc(in)));
		switch(ord){
			case 'M':Move();break;
			case 'I':Insert();break;
			case 'D':Del();break;
			case 'G':Get();break;
			case 'P':ptr.prev();break;
			default :ptr.next();break;
		}
	}
	#if defined DEBUG
	cout << endl << (double)clock() / CLOCKS_PER_SEC <<" sec" << endl;
	#endif
	return 0;
}