用treap記錄字首哈希值，二分求最大值
#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
//
const int P1=1e7+7;
const int B1=194317;
int Pow1[ 110000 ];
int Pow2[ 110000 ];
struct TreeNode {
TreeNode *L,*R,*fa;
int siz;
int pri;
int ch;
int has;
};
TreeNode nodes[maxn*3];
int cnt_node;
TreeNode* create(int ch,int pri){
++cnt_node;
TreeNode* tmp=&nodes[ cnt_node ];
tmp->L=NULL;
tmp->R=NULL;
tmp->fa=NULL;
tmp->siz=1;
tmp->pri=pri;
tmp->ch=ch;
tmp->has=ch;
return tmp;
}
void update(TreeNode* now)
{
now->siz=1;
now->has=now->ch;
if ( now->L !=NULL )
{
now->siz+=now->L->siz;
now->has=(now->ch+1ll*now->L->has*B1 )%P1;
now->L->fa=now;
}
if ( now->R !=NULL )
{
now->siz+=now->R->siz;
now->has=(1ll*now->has*Pow1[ now->R->siz ]%P1+1ll*now->R->has)%P1;
now->R->fa=now;
}
}
void out(TreeNode* now){
if ( now==NULL ) return ;
out(now->L);
printf("ch=%d siz=%d hash=%d pri=%d\n",now->ch,now->siz,now->has,now->pri);
out(now->R);
}
TreeNode* get_kth(TreeNode *now,int k){
if ( now->siz<k ) return NULL;
while ( now!=NULL )
{
if (now->L!=NULL )
if ( now->L->siz >= k )
{
now=now->L;
continue;
}
else
k-=now->L->siz;
if ( 1 >= k )
return now;
k-=1;
now=now->R;
}
return now;
}
TreeNode* Merge(TreeNode* A , TreeNode* B) {
if (A == NULL)
return B;
if (B == NULL)
return A;
if (A->pri < B->pri) {
A->R = Merge(A->R, B);
update(A); update(B);
return A;
} else {
B->L = Merge(A, B->L);
update(A); update(B);
return B;
}
}
pair<TreeNode*, TreeNode*> split(TreeNode* now, int key) {
if ( key==0 )
return make_pair((TreeNode*)NULL,now);
pair<TreeNode*, TreeNode*> tmp;
if (now == NULL) {
tmp = make_pair( (TreeNode* )NULL, (TreeNode* )NULL);
return tmp;
}
if ( ( now->L!=NULL ) && (key <= now->L->siz) )
{
tmp = split(now->L, key);
now->L = tmp.second;
tmp.second = now;
} else {
if ( now->L != NULL )
key-=now->L->siz;
key--;
tmp = split(now->R, key);
now->R = tmp.first;
tmp.first = now;
}
update(now);
return tmp;
}
inline void read(int &x){
char ch;
bool flag = false;
for (ch = getchar(); !isdigit(ch); ch = getchar())if (ch == '-') flag = true;
for (x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
x = flag ? -x : x;
}
const int P=1e7+7;
int get_rand(){
return 1ll*rand()*rand()%P;
}
const int MAXN=200100;
int n,m;
char s[ MAXN ];
char op[ MAXN ];
char t[ MAXN ];
TreeNode* root;
void build(int l,int r){
if ( l>r ) return ;
int mid=(l+r)/2;
build(l,mid-1);
TreeNode* tmp=create(s[mid]-'a'+1,get_rand());
root=Merge(root,tmp);
build(mid+1,r);
}
int get_kth_has(TreeNode *now,int k){
if ( k==0 ) return 0;
if ( now->siz<k ) return 0;
long long ans=0;
while ( now!=NULL )
{
if (now->L!=NULL )
if ( now->L->siz >= k )
{
now=now->L;
continue;
}
else
{
k-=now->L->siz;
ans=(ans+1ll*Pow1[k]*now->L->has%P1)%P1;
}
k--;
ans=(ans+1ll*now->ch*Pow1[k]%P1)%P1;
if ( 0 >= k )
return ans;
now=now->R;
}
return ans;
}
int get_has(int has_st,int ed,int len){
long long has=get_kth_has(root,ed);
has=(has-1ll*has_st*Pow1[len]%P1 )%P1;
if ( has<0 )
has=has+P1;
return has;
}
int sum=0;
int get_ans(int x,int y){
int l=1,r=root->siz-max(x,y)+1;
int ans=0;
int has_x=get_kth_has(root,x-1);
int has_y=get_kth_has(root,y-1);
while ( l<=r )
{
int mid=(l+r)/2;
if ( get_has(has_x,x+mid-1,mid) == get_has(has_y,y+mid-1,mid) )
{
l=mid+1;
ans=mid;
}
else
r=mid-1;
}
return ans;
}
inline void write(int x) {
static const int maxlen = 100;
static char s[maxlen];
if (x < 0) { putchar('-'); x = -x;}
if (!x) { putchar('0'); return; }
int len = 0; for (; x; x /= 10) s[len++] = x % 10 + '0';
for (int i = len - 1; i >= 0; --i) putchar(s[i]);
}
int dfs(TreeNode* now){
int deep=0;
if ( now->L !=NULL ) deep=max(deep,dfs(now->L)+1);
if ( now->R !=NULL ) deep=max(deep,dfs(now->R)+1);
return deep;
}
int main(){
Pow1[0]=1;
Pow2[0]=1;
for (int i=1;i<=1e5;i++)
Pow1[i]=1ll*Pow1[i-1]*B1%P1;
scanf("%s",s);
n=strlen(s);
root=NULL;
build(0,n-1);
read(m);
for (int i=1;i<=m;i++)
{
scanf("%s",op);
if ( op[0]=='R' )
{
int x;read(x);
scanf("%s",t);
TreeNode* tmp=get_kth(root,x);
tmp->ch=t[0]-'a'+1;
while ( tmp!=NULL )
{
update(tmp);
tmp=tmp->fa;
}
}
else
if ( op[0]=='I' )
{
int x;read(x);
scanf("%s",t);
TreeNode* tmp;
tmp=create(t[0]-'a'+1,get_rand());
if ( x==0 )
root=Merge(tmp,root);
else
{
TreeNode* now=get_kth(root,x);
now->R=Merge(tmp,now->R);
while ( now!=NULL )
{
update(now);
now=now->fa;
}
}
}
else
{
int x,y;
read(x);read(y);
write(get_ans(x,y));
puts("");
}
}
return 0;
}