记录编号	360817	评测结果	AAAAAAAAAA
题目名称	[JSOI 2008]火星人prefix	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	9.168 s
提交时间	2017-01-01 16:08:59	内存使用	30.30 MiB

#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ll;
const int N=5e5+10,NP=3;
const ll p[NP]={1e6+7,1e7+7,1e8+7};
char str[N],ch[10];int x,y;
int n,q,son[N][2],fa[N],k[N],s[N],Root,top;
bool root[N];
ll hs[N][NP],mi[N][NP];
#define lc son[x][0]
#define rc son[x][1]
void update(int x){
	s[x]=s[lc]+s[rc]+1;
	for (int j=0;j<NP;j++)
		hs[x][j]=((hs[lc][j]*26+k[x])*mi[s[rc]][j]+hs[rc][j])%p[j];
}
void New(int Fa,int K){//插入右子树 
	k[++top]=K;
	fa[son[Fa][1]=top]=Fa;
	update(top);
}
void rot(int x){
	int y=fa[x],z=fa[y];
	bool b=(x==son[y][1]);
	fa[son[y][b]=son[x][!b]]=y;
	fa[son[x][!b]=y]=x;
	fa[x]=z;
	if (son[z][0]==y) son[z][0]=x;else
	if (son[z][1]==y) son[z][1]=x;
	root[x]=root[y];root[y]=0;
	update(y);update(x);
}
void splay(int x){
	while (fa[x]){
		int y=fa[x],z=fa[y];
		if (root[y]||root[z]){rot(x);continue;}
		if (y==son[z][0]) rot(x==son[y][0]?y:x);
			else rot(x==son[y][1]?y:x);
		rot(x);
	}
	Root=x;
}
void find(int key){
	int x=Root;
	while (1){
		int i=s[lc]+1;
		if (i==key) break;
		if (key>i) key-=i,x=rc;
			else x=lc;
	}
	splay(x);
}
void hash(int x,int L,ll *ans){//以x开头，长为L的hash值 
	find(x);find(x+L+1);
	int le=son[Root][0],th=son[le][1];
	for (int j=0;j<NP;j++) ans[j]=hs[th][j];
}
void insert(int p,int c){
	find(p+1);
	find(p+2);
	int le=son[Root][0];
	New(le,c);
	update(le);update(Root);
	++n;
}
void change(int p,int c){
	find(p+1);
	k[Root]=c;
	update(Root);
}
int lcp(int x,int y){
	int l=0,r=n+1-max(x,y);
	ll hsx[NP],hsy[NP];
	while (l!=r){
		int mid=(l+r)>>1;
		hash(x,mid+1,hsx);
		hash(y,mid+1,hsy);
		bool check=1;
		for (int j=0;j<NP;j++)
		if (hsx[j]!=hsy[j]) check=0;
		if (check) l=mid+1;else r=mid;
	}
	return l;
}
void init(){
	for (int j=0;j<NP;j++) mi[0][j]=1;
	for (int i=1;i<=1e5;i++)
	for (int j=0;j<NP;j++)
		mi[i][j]=mi[i-1][j]*26%p[j];
	s[1]=2;s[2]=1;top=2;
	fa[son[1][1]=2]=1;
	root[Root=1]=1;
}
int main()
{
	freopen("bzoj_1014.in","r",stdin);
	freopen("bzoj_1014.out","w",stdout);
	init();
	scanf("%s%d",str+1,&q);
	int len=strlen(str+1);
	for (int i=1;i<=len;i++) insert(i-1,str[i]-'a');
	while (q--){
		scanf("%s%d",ch,&x);
		if (ch[0]=='Q')
			scanf("%d",&y),printf("%d\n",lcp(x,y));
		else
		if (ch[0]=='R')
			scanf("%s",ch),change(x,ch[0]-'a');
		else
		if (ch[0]=='I')
			scanf("%s",ch),insert(x,ch[0]-'a');
	}
	return 0;
}