题意

维护一个由小写字母构成的字符串，要求支持单点修改，插入单个字符，查询两个后缀的\(LCP\)

思路

LCP是可以用二分+hash检验的，支持插入操作自然可以想到平衡树，由于hash可以使用线段树或者平衡树维护，所以本题平衡树+二分即可

本题需要一定卡常

Code

#include
    
     #define N 400005using namespace std;typedef unsigned int ULL;const ULL tp = 1000000007;int n,m,root;char a[N];ULL po[N];struct T{    int size,ch[2],key;    ULL val,sum;}t[N];int cnt;template 
     
      void read(T &x){    char c;int sign=1;    while((c=getchar())>'9'||c<'0') if(c=='-') sign=-1; x=c-48;    while((c=getchar())>='0'&&c<='9') x=x*10+c-48; x*=sign;}inline void update(int x){    t[x].size=t[t[x].ch[0]].size+t[t[x].ch[1]].size+1;    t[x].sum=t[t[x].ch[1]].sum + t[x].val*po[t[t[x].ch[1]].size] + t[t[x].ch[0]].sum*po[t[t[x].ch[1]].size+1];}inline int add_node(int x){    ++cnt;    t[cnt].ch[0]=t[cnt].ch[1]=0;    t[cnt].key=rand(); t[cnt].size=1;    t[cnt].sum=t[cnt].val=x;    return cnt;}int merge(int l,int r){    if(!l||!r) return l+r;    if(t[l].key
      
       y) swap(x,y);    int l=1,r=n-y+1,ans=0;    while(l<=r)    {        int mid=(l+r)>>1;        if(ask(x,x+mid-1)==ask(y,y+mid-1)) l=mid+1,ans=mid;        else r=mid-1;    }    return ans;}int main(){    srand((unsigned)time(NULL));srand(rand());    po[0]=1;    for(int i=1;i<=200000;++i) po[i]=po[i-1]*tp;         scanf("%s",a);    n=strlen(a);    for(int i=1;i<=n;++i) add(i-1,a[i-1]-'a'+1);//建树         read(m);    while(m--)    {        char op[2];        scanf("%s",op);        if(op[0]=='Q')//询问         {            int x,y; read(x); read(y);            printf("%d\n",query(x,y));        }        else if(op[0]=='R')//修改         {            int x; read(x); scanf("%s",op);            del(x);            add(x-1,op[0]-'a'+1);        }        else//插入         {            ++n;            int x; read(x); scanf("%s",op);            add(x,op[0]-'a'+1);        }    }    return 0;}