记录编号	146175	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]火星人prefix	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	3.979 s
提交时间	2015-01-13 07:41:41	内存使用	4.46 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#define l(x) ch[x][0]
#define r(x) ch[x][1]
#define Maxn 150010
//#define Mod 9875321
#define LL long long
using namespace std;
int ch[Maxn][2],n,m,root,tot=0,fa[Maxn];
int siz[Maxn],v[Maxn];
unsigned int p[Maxn],h[Maxn];
char str[Maxn];
void qread(int &x){
	char c; int f=1;
	while(c=getchar(),!isdigit(c)) if(c=='-') f=-1; x=c-'0';
	while(c=getchar(),isdigit(c)) x=10*x+c-'0'; x*=f;
}
void update(int x){
	siz[x]=siz[l(x)]+siz[r(x)]+1;
    h[x]=h[l(x)]+(LL)v[x]*p[siz[l(x)]]+(LL)p[siz[l(x)]+1]*h[r(x)];
}
void rotate(int x,int &k){
	int y=fa[x],z=fa[y],l,r;
	if(l(y)==x) l=0; else l=1; r=l^1;
	if(y==k) k=x;
	else{if(l(z)==y) l(z)=x; else r(z)=x;}
	fa[x]=z; fa[y]=x; fa[ch[x][r]]=y;
	ch[y][l]=ch[x][r]; ch[x][r]=y;
	update(y); update(x);
}
void splay(int x,int &k){
	while(x!=k){
		int y=fa[x],z=fa[y];
		if(y!=k){
			if(l(y)==x^r(z)==y) rotate(x,k);
			else rotate(y,k);
		}
		rotate(x,k);
	}
}
int findk(int x,int k){
	if(siz[l(x)]+1==k) return x;
	else if(siz[l(x)]>=k) return findk(l(x),k);
	return findk(r(x),k-siz[l(x)]-1);
}
void insert(int k,int val){
	int x=findk(root,k+1),y=findk(root,k+2);
	splay(x,root); splay(y,r(x));
	int now=++tot; l(y)=now; fa[now]=y; v[now]=val;
	update(now); update(y); update(x);
}
int queryh(int k,int val){
	int x=findk(root,k),y=findk(root,k+val+1);
	splay(x,root); splay(y,r(x));
	return h[l(y)];
}
int LCP(int x,int y){
	int l=1,r=min(tot-x,tot-y)-1,res=0;
	while(l<=r){
		int mid=(l+r)>>1;
		if(queryh(x,mid)==queryh(y,mid)) l=mid+1,res=mid;
		else r=mid-1;
	}
	return res;
}
void build(int l,int r,int last){
	if(l>r) return;
	int now=l;
	if(l==r){
		v[now]=h[now]=str[l]-'a'+1;
		fa[now]=last; siz[now]=1;
		if(l<last) l(last)=now;
		else r(last)=now;
		return;
	}
	int mid=(l+r)>>1; now=mid;
	build(l,mid-1,mid); build(mid+1,r,mid);
	v[now]=str[mid]-'a'+1; fa[now]=last; update(now);
	if(mid<last) l(last)=now; else r(last)=now;
}
void work(){
	char a[4],b[4];
	qread(m);
	for(int i=1,x,y;i<=m;i++){
		scanf("%s",a+1); qread(x);
		if(a[1]=='Q'){
			qread(y);
			printf("%d\n",LCP(x,y));
		}
		else if(a[1]=='R'){
			scanf("%s",b+1); x=findk(root,x+1);
			splay(x,root); v[root]=b[1]-'a'+1;
			update(root);
		}
		else{
			scanf("%s",b+1);
			insert(x,b[1]-'a'+1);
		}
	}
}
void init(){
	scanf("%s",str+2);
	n=strlen(str+2); p[0]=1;
	for(int i=1;i<=150000;i++) p[i]=p[i-1]*27;
	build(1,n+2,0);
	tot=n+2; root=(n+3)>>1;
}
int main(){
	freopen("bzoj_1014.in","r",stdin);
	freopen("bzoj_1014.out","w",stdout);
	init();
	work();
	return 0;
}