题意分析

1. 初始文本处理：
   • 给定一个初始文本字符串，支持插入字符和查询操作。
2. 查询要求：
   • $Q$ $i$ $j$：求从初始文本（未插入新字符）的第$i$个和第$j$个字符开始的最长公共前缀（$LCP$）长度。
3. 插入操作：
   • $I$ $ch$ $p$：在文本的指定位置插入字符，但插入的字符不影响后续$Q$命令的查询（仅基于初始文本）。

解题思路

1. 问题核心：
   • 对于$Q$ $i$ $j$，实质是求初始文本的两个后缀的最长公共前缀。
   • 插入操作仅影响文本的物理存储，不改变初始文本的索引逻辑。
2. 高效查询：
   • 预处理初始文本的后缀数组（$Suffix$ $Array$）或哈希表，以支持快速LCP查询。
   • 使用$RMQ$$（Range Minimum Query）$或二分+哈希优化$LCP$计算。
3. 插入处理：
   • 由于插入操作较少（$200$次），可直接暴力维护文本，但查询时需忽略插入的字符。

实现步骤

1. 初始文本存储：
   • 保存初始文本，并记录其长度$L_0$。
2. 插入操作处理：
   • 维护一个动态字符串，但$Q$命令仅基于初始文本的$1$到$L_0$字符。
3. 查询处理：
   • 对每个$Q$ $i$ $j$，计算初始文本的子串$S[i...]$和$S[j...]$的$LCP$：
     • 方法1：暴力匹配，时间复杂度$O(\text{ans})$，最坏$O(L_0)$。
     • 方法2：基于后缀数组的$O(1)$ LCP查询（需预处理）。
4. 输出结果：
   • 对每个$Q$命令直接输出$LCP$长度。

代码实现

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=100000;
unsigned long long hashs[maxn],pw[maxn];
char inp[maxn];
int len,old[maxn],nowlen;
void build(int s){
    for(int i=s;i<=nowlen;i++)
        hashs[i]=hashs[i-1]*131+inp[i];
}

int query(int a,int b){
    if(a>b) swap(a,b);
    int l=0,r=nowlen-b+1,mid;   //此处要把 l 和 r 之间的距离尽量压缩，不然会WA
    int ans=0;
    while(l<r){
        mid=(l+r+1)/2;  //此处令mid稍微右偏，然后 r 修改的时候用 r=mid-1，稍微左偏，提高精度，不然也会WA
        if(hashs[a+mid-1]-hashs[a-1]*pw[mid]==hashs[b+mid-1]-hashs[b-1]*pw[mid])    l=mid,ans=mid;
        else    r=mid-1;
    }
    return ans;
}
int main(){
    int have,a,b;
    char ord[5],ins[5];
    scanf("%s",inp+1);
    scanf("%d",&have);
    nowlen=strlen(inp+1);
    len=nowlen;
    pw[0]=1;
    for(int i=1;i<=len+250;i++) pw[i]=pw[i-1]*131;
    for(int i=1;i<=len;i++) old[i]=i;
    build(1);
    for(int j=0;j<have;j++){
        scanf("%s",ord);
        if(ord[0]=='Q'){
            scanf("%d%d",&a,&b);
            printf("%d\n",query(old[a],old[b]));
        }
        else{
            scanf("%s %d",ins,&a);
            if(a>nowlen)    a=nowlen+1;
            for(int i=nowlen;i>=a;i--)   inp[i+1]=inp[i];
            inp[a]=ins[0];nowlen++;
            build(a);
            for(int i=len;i>=1;i--){
                if(old[i]>=a)   old[i]++;
                else    break;
            }
        }
    }
    return 0;
}