记录编号	496707	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2015] Persistable Editor	最终得分	100
用户昵称	LadyLex	是否通过	通过
代码语言	C++	运行时间	1.251 s
提交时间	2018-05-06 20:13:20	内存使用	0.70 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;
const int N=100005;
int d,cnt;char s[250];
struct Treap
{
	Treap *ch[2];
	char val;int size,key;
	Treap(){val=size=0;key=rand();ch[0]=ch[1]=NULL;}
	inline void update(){size=ch[0]->size+ch[1]->size+1;}
}*null=new Treap(),*root[N];
inline Treap* newTreap(char c)
{
	Treap *o=new Treap();o->ch[0]=o->ch[1]=null;
	o->val=c;o->size=1;return o;
}
inline void cop(Treap *&a,Treap *b)
{
	if(b==null)a=null;
	else a=newTreap(0),*a=*b;
}
void split(Treap *rt,Treap *&a,Treap *&b,int k)
{
	if(!k)cop(b,rt),a=null;
	else if(rt->size<=k)cop(a,rt),b=null;
	else if(rt->ch[0]->size>=k)
		cop(b,rt),split(rt->ch[0],a,b->ch[0],k),b->update();
	else cop(a,rt),split(rt->ch[1],a->ch[1],b,k-rt->ch[0]->size-1),a->update();
}
void merge(Treap *&rt,Treap *a,Treap *b)
{
	if(a==null)cop(rt,b);
	else if(b==null)cop(rt,a);
	else if(a->key < b->key)
		cop(rt,a),merge(rt->ch[1],a->ch[1],b),rt->update();
	else 
		cop(rt,b),merge(rt->ch[0],a,b->ch[0]),rt->update();
}
void dfs(Treap *o)
{
	if(o==null)return;
	dfs(o->ch[0]);
	printf("%c",o->val);
	if(o->val=='c')d++;
	dfs(o->ch[1]);
}
void check(Treap *o)
{
	if(o==null)return;
	check(o->ch[0]);
	printf("%c",o->val);
	check(o->ch[1]);
}
inline void print()
{
	int mk,p,x;
	scanf("%d%d%d",&mk,&p,&x);mk-=d,p-=d,x-=d;
	Treap *a,*b,*c;
	split(root[mk],a,b,p-1),split(b,b,c,x);
	dfs(b);printf("\n");
	//merge(a,a,b),merge(root[mk],a,c);
}
inline Treap* build(char *t)
{
	static Treap *stack[210],*x,*last;
	int p=0,m=strlen(t);
	for(int i=0;i<m;i++)
	{
		x=newTreap(s[i]);last=null;
		while(p&&stack[p]->key > x->key)
			stack[p]->update(),last=stack[p--];
		if(p)stack[p]->ch[1]=x;
		x->ch[0]=last;stack[++p]=x;
	}
	while(p)stack[p--]->update();
	return stack[1];
}
inline void insert()
{
	int p;scanf("%d%s",&p,s);p-=d;
	Treap *a,*b,*c=build(s);
	split(root[cnt],a,b,p);
	merge(a,a,c);
	merge(root[++cnt],a,b);
}
inline void del()
{
	int p,x;scanf("%d%d",&p,&x);
	p-=d,x-=d;
	Treap *a,*b,*c;
	split(root[cnt],a,b,p-1);
	split(b,b,c,x);
	merge(root[++cnt],a,c);
}
int main()
{
	freopen("persistable_editor.in","r",stdin);
	freopen("persistable_editor.out","w",stdout);
	int n,opt;scanf("%d",&n);
	null->ch[0]=null->ch[1]=null;
	for(int i=0;i<=n;i++)root[i]=null;
	while(n--)
	{
		scanf("%d",&opt);
		switch(opt)
		{
			case 1:insert();break;
			case 2:del();break;
			case 3:print();break;
		}
	}
}