记录编号	440759	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[HZOI 2015] Persistable Editor	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.986 s
提交时间	2017-08-24 08:01:39	内存使用	96.13 MiB

//可持久化数据结构研究——陈立杰
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<ctime>
using namespace std;
const int N=1e5+10,M=5e6+10;
struct node{int l,r,v,s,ran;}nd[M];
int n,root[N],id,version;
#define lc nd[x].l
#define rc nd[x].r
char str[N];int key;
void print(int x,bool c=1){
	if (!x) return;
	if (lc) print(lc,c);
	putchar(nd[x].v);
	if (c&&nd[x].v=='c') key++;
	if (rc) print(rc,c);
}
int merge(int x,int y){
	if (!x||!y) return x|y;
	int now=++id;
	if (nd[x].ran>nd[y].ran){
		nd[now]=nd[x];
		nd[now].s+=nd[y].s;
		nd[now].r=merge(nd[x].r,y);
	}
	else{
		nd[now]=nd[y];
		nd[now].s+=nd[x].s;
		nd[now].l=merge(x,nd[y].l);
	}
	return now;
}
void split(int x,int &lt,int &rt,int k){
	if (!x){lt=rt=0;return;}
	int s=nd[lc].s+1;
	int root=++id;
	nd[root]=(node){0,0,nd[x].v,1,nd[x].ran};
	if (k==s){lt=merge(lc,root);rt=rc;return;}
	if (k>s){
		split(rc,lt,rt,k-s);
		lt=merge(merge(lc,root),lt);
	}
	else{
		split(lc,lt,rt,k);
		rt=merge(rt,merge(root,rc));
	}
}
void split(int x,int l,int r,int &lt,int &mt,int &rt){
	int now;
	split(x,lt,now,l-1);
	split(now,mt,rt,r-l+1);
}
int main()
{
	freopen("persistable_editor.in","r",stdin);
	freopen("persistable_editor.out","w",stdout);
	srand((unsigned)time(0));
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		//printf("opt %d\n",i);
		int tp,x,p,c;
		scanf("%d",&tp);
		int lt,mt,rt;
		if (tp==1){
			scanf("%d%s",&p,str);p-=key;
			int len=strlen(str);
			split(root[version],lt,rt,p);
			for (int i=0;i<len;i++){
				nd[++id]=(node){0,0,str[i],1,rand()};
				lt=merge(lt,id);
			}
			root[++version]=merge(lt,rt);
		}
		if (tp==2){
			scanf("%d%d",&p,&c);p-=key;c-=key;
			split(root[version],p,p+c-1,lt,mt,rt);
			root[++version]=merge(lt,rt);
		}
		if (tp==3){
			scanf("%d%d%d",&x,&p,&c);x-=key;p-=key;c-=key;
			split(root[x],p,p+c-1,lt,mt,rt);
			print(mt);puts("");
		}
	}
	return 0;
}