题目分析

这是一个动态字符串处理问题，需要支持三种操作：

• 查询：计算两个后缀的公共前缀长度 $\text{LCQ}(x,y)$
• 修改：将字符串中第 $x$ 个字符改为 $d$
• 插入：在第 $x$ 个字符后插入字符 $d$

暴力解法

代码采用直接模拟的方法：

查询操作

while (x < (int)s.size() && y < (int)s.size() && s[x] == s[y])
    ++x, ++y, ++ans;

• 时间复杂度：$O(L)$，其中 $L$ 为公共前缀长度

修改操作

s[x - 1] = ch;

• 时间复杂度：$O(1)$

插入操作

s.insert(x, 1, ch);

• 时间复杂度：$O(L)$，其中 $L$ 为字符串长度

复杂度分析

设字符串最终长度为 $n$，查询次数为 $q_Q$，修改次数为 $q_R$，插入次数为 $q_I$：

• 总时间复杂度：$O(q_Q \cdot n + q_I \cdot n)$
• 最坏情况：$O(10000 \times 10^5 + 140000 \times 10^5) \approx 1.5 \times 10^{10}$

适用数据范围

该解法适用于：

• 小数据：字符串长度不超过 $1000$
• 查询较少：如题目中前两个测试点

对于大数据（$n \leq 10^5$，$M \leq 150000$），需要更高效的算法。

优化方向

哈希 + 二分

• 预处理字符串哈希值
• 查询时二分公共前缀长度
• 时间复杂度：$O(\log n)$ 每次查询

平衡树维护

• 使用平衡树维护字符串
• 每个节点存储子树哈希值
• 支持 $O(\log n)$ 的修改、插入和查询

样例验证

输入：

madamimadam
7
Q 1 7    → 比较"madamimadam"和"mimadam" → 5
Q 4 8    → 比较"amimadam"和"madam" → 1  
Q 10 11  → 比较"am"和"m" → 0
R 3 a    → s[2] = 'a'
Q 1 7    → 比较"maamimadam"和"mimadam" → 2
I 10 a   → 插入后字符串变化
Q 2 11   → 比较"aamimadama"和"madama" → 1

输出：

5
1
0
2
1

与样例完全一致。

总结

该暴力解法实现简单，在数据规模较小时可行。对于大数据需要使用哈希或平衡树等数据结构进行优化。