RT，大概思路使用Treap维护子树代表的字符串的hash值

经过对拍发现错误出在修改操作上，修改后给出的询问答案有些会比正确答案要大。
但如果将询问所需要用到的所有字符一个个从Treap中分裂出来，再一个个合并回去，就会得到正确答案
个人猜测可能是有些地方没有 push_up

求DeBug QwQ

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef unsigned long long ull;
const int Maxn=5e5+10;
const ull base=27;
ull sum[Maxn]; //子树哈希值
int s[Maxn],a[Maxn];
int ls[Maxn],rs[Maxn];
int p[Maxn],f[Maxn];
int n,m,idcnt,root;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
inline void push_up(int x)
{
	s[x]=s[ls[x]]+s[rs[x]]+1;
	sum[x]=sum[ls[x]]*base+(ull)a[x];
	sum[x]=sum[x]*f[s[rs[x]]]+sum[rs[x]];
}
void split(int x,int k,int &u,int &v)
{
	if(!x){u=v=0;return;}
	int tmp=s[ls[x]]+1;
	if(tmp<=k)u=x,split(rs[x],k-tmp,rs[x],v);
	else v=x,split(ls[x],k,u,ls[x]);
	push_up(x);
}
int merge(int x,int y)
{
	if(x)push_up(x);
	if(y)push_up(y);
	if(!x || !y)return x|y;
	if(p[x]<p[y])
	{
		rs[x]=merge(rs[x],y);
		push_up(x);return x;
	}
	else
	{
		ls[y]=merge(x,ls[y]);
		push_up(y);return y;
	}
}
void ins(int x,int k) //插入元素
{
	int u,v;
	split(root,k-1,u,v);
	root=merge(merge(u,x),v);
}
void modify(int k,int v)// 修改元素
{
	int x,y,z;
	split(root,k,x,z);
	split(x,k-1,x,y);
	y=++idcnt,p[y]=rand();
	a[y]=v,push_up(y);
	root=merge(merge(x,y),z);
}
ull query(int l,int r) // 询问区间 [l,r] 的哈希值
{
	int x,y,z;
	split(root,r,x,z);
	split(x,l-1,x,y);
	ull ret=sum[y];
	root=merge(merge(x,y),z);
	return ret;
}
void input()
{
	char s[Maxn];
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;++i)
	{
		int x=++idcnt;
		p[x]=rand(),a[x]=s[i]-'a'+1;
		push_up(x),ins(x,i);
	}
}
int calc(int x,int y) 计算以 x,y 开头的后缀的lcp长度
{
	if(query(x,x)!=query(y,y))return 0;
	int l=0,r=min(n-x,n-y);
	while(l<r)
	{
		int mid=(l+r)>>1;++mid;
		if(query(x,x+mid)!=query(y,y+mid))r=mid-1;
		else l=mid;
	}
	return l+1;
}
int main()
{
	// freopen("in.txt","r",stdin);
	// freopen("out.txt","w",stdout);
	input(),m=read(),f[0]=1;
	for(int i=1;i<=min(100000,n+m);++i)
	f[i]=f[i-1]*base;
	int tot=0;
	while(m--)
	{
		char opt=getchar();
		while(opt<'A' || opt>'Z')
		opt=getchar();
		if(opt=='Q')
		{
			++tot;
			int x=read(),y=read();
			// if(tot==6555)
			// {
			// 	printf("check %d %d\n",x,y);
			// 	for(int i=x;i<x+4;++i)
			// 	putchar(query(i,i)+'a'-1);
			// 	putchar('\n');
			// 	for(int i=y;i<y+4;++i)
			// 	putchar(query(i,i)+'a'-1);
			// 	putchar('\n');
			// 	cout<<"calc "<<query(x,x+3)<<' '<<query(y,y+3)<<endl;
			// 	printf("%d\n",calc(x,y));
			// }
			printf("%d\n",calc(x,y));
			// if(calc(x,y)==4)printf("tot = %d\n",tot);
			continue;
		}
		int x=read();
		char tmp=getchar();
		while(tmp<'a' || tmp>'z')
		tmp=getchar();
		int v=tmp-'a'+1;
		if(opt=='R')modify(x,v);
		else
		{
			int k=x;x=++idcnt;
			p[x]=rand(),a[x]=v,++n;
			push_up(x),ins(x,k+1);
		}
	}
	return 0;
}

PS：这里 是一组hack数据，错误出在第 $6555$ 条询问上
提取码 qbdb