1. 前缀比较具有二分性 (左对右错) 2. 字符串哈希具有结合律 3. fhq-treap 中序就是字符串原来的序列 4. 利用fhq-treap 的logn 分裂合并的性质维护 动态插入与删除 与 结合律
OJ: luogu
题目 ID: P4036
难度:省选/NOI-
目录
形式化题目
给定一个可修改、可插入字符的字符串。对任意位置
这里先忽略修改和插入，研究一个静态字符串中：后缀排好序后，为什么 LCQ 可以快速查询。
第一个关键观察：排序后求 LCQ
把每个位置看成一个后缀
以样例字符串 madamimadam 为例。位置
将全部后缀按字典序排序，得到：
| 排名 | 起点 | 后缀 |
|---|---|---|
| 1 | 8 | adam |
| 2 | 2 | adamimadam |
| 3 | 10 | am |
| 4 | 4 | amimadam |
| 5 | 9 | dam |
| 6 | 3 | damimadam |
| 7 | 6 | imadam |
| 8 | 11 | m |
| 9 | 7 | madam |
| 10 | 1 | madamimadam |
| 11 | 5 | mimadam |
记 sa[k] 为排名第
也就是说，height[k] 只记录排序表中第 height 依次为：
| 相邻排名 | 公共前缀 | LCP |
|---|---|---|
adam |
4 | |
a |
1 | |
am |
2 | |
| 无 | 0 | |
dam |
3 | |
| 无 | 0 | |
| 无 | 0 | |
m |
1 | |
madam |
5 | |
m |
1 |
排名相邻时，答案就是对应的 height
查询
S_1 = madamimadam，排名 10
S_7 = madam， 排名 9它们在排序表中相邻。因此直接查看 madam。
同样，
S_2 = adamimadam，排名 2
S_10 = am， 排名 3它们也相邻，所以答案是 a。注意：这个例子是相邻后缀，不能用来说明区间最小值。
排名不相邻时，取中间 height 的最小值
若两个后缀的排名为
例如查询
S_4 = amimadam，排名 4
S_7 = madam， 排名 9需要取
0, 3, 0, 0, 1最小值是 a 开头，另一个以 m 开头。
为什么一定是最小值？
设两端后缀
在字典序中，所有同样以这段前缀开头的字符串会连成一段；因此，排在这两个后缀之间的每一个后缀，也都以这
反过来，如果区间内每对相邻后缀都至少有
两边合起来，区间最小值恰好就是两端后缀的 LCQ。
静态字符串如何变成快速查询
静态时可以按下面的路线预处理：
- 建立后缀数组
sa，并记录每个起点的排名rank。 - 建立相邻后缀的 LCP 数组
height。 - 查询
时，先得到 ；交换使 。 - 查询
height[l+1..r]的最小值。用 RMQ 预处理后，每次可做到或 。
这解释了题面所说的“后缀排好序后，可以很快求 LCQ”。但本题还会修改、插入字符：后缀排序与 height 都会随之失效，后续需要寻找能动态维护这一性质的结构。
正解
思路
后缀数组适合静态字符串，但修改第
换一个问法：对于给定的长度
二分中的判定需要比较两个等长子串。用多项式哈希表示字符串
本题还要在任意位置插入，所以普通前缀哈希数组不能使用。将字符串放入隐式 FHQ Treap：Treap 的中序遍历就是当前字符串，而不是按字符大小排序。每个节点维护：
size：子树字符数量，用来按“前个字符”分裂； hash_value：整棵子树对应字符串的哈希。
若节点的左右子树长度分别为
这样，split(root,k) 把字符串切成前 size 定位目标节点，再自底向上重算哈希，二者期望复杂度均为
为避免二分时频繁拆树，代码中的 range_hash 直接沿 Treap 查询区间哈希：完全被覆盖的子树直接使用其 hash_value，只有区间两端各走一条树链，所以期望也是
二分上界为两个后缀中较短者的长度。这里使用
正确性说明
对每个节点，pull 按“左子串 + 当前字符 + 右子串”的拼接公式更新 size 和哈希。因此归纳可知，任一子树的 hash_value 始终等于其中序字符序列的哈希；range_hash 将若干从左到右的完整片段按同一拼接公式合并，故得到目标子串的哈希。
split 按左子树大小决定当前节点属于哪一部分，故返回的两棵树恰好对应原字符串的前 merge 只连接左段与右段，保持中序顺序不变。修改按 size 找到唯一的第 pull 祖先。因此插入与修改后，Treap 中序遍历始终等于当前字符串。
设 check(k) 表示位置 check(k) 单调。二分找到的最大真值
实现对应
main.cpp 采用数组内存池保存 Treap 节点，tr[0] 是空节点，默认 siz=0,hash_value=0。这使 push_up 不必对左右儿子分别判空。
| 函数 | 它在题目中的含义 |
|---|---|
split(u,k,x,y) |
将以 u 为根的字符串切成前 |
merge(x,y) |
按原顺序拼接两个相邻字符串段 |
push_up(u) |
重新计算该子树的长度和整段哈希 |
range_hash(u,l,r) |
获取子树内第 |
insert_after |
处理 I x d，在第 |
change |
处理 R x d，按排名找到第 |
check |
判断两个长度为 len 的前缀是否相同，供二分调用 |
first_fail(left,right) |
由二分模板改造，寻找第一个 check(len) 为假的长度；答案减一 |
哈希使用 unsigned long long。C++ 中无符号整数溢出按模
代码
/**
* Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
* rbook: -> https://rbook.roj.ac.cn https://rbook2.roj.ac.cn
* rainboy的学习导航网站: https://idx.roj.ac.cn
* create_at: 2026-09-15 14:26
* update_at: 2026-09-15 16:59
*/
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int maxn = 250000 + 5;
const ull base = 233;
struct Node {
int l, r;
int siz;
int val;
unsigned int fix;
ull hash_value;
} tr[maxn];
int root, node_cnt;
int m;
int query_x, query_y;
ull pw[maxn];
mt19937 rnd(712367821);
int new_node(int val) {
node_cnt++;
tr[node_cnt].l = tr[node_cnt].r = 0;
tr[node_cnt].siz = 1;
tr[node_cnt].val = val;
tr[node_cnt].fix = rnd();
tr[node_cnt].hash_value = val;
return node_cnt;
}
// 维护“左子串 + 当前字符 + 右子串”的长度与哈希。
void push_up(int u) {
int left_siz = tr[tr[u].l].siz;
int right_siz = tr[tr[u].r].siz;
tr[u].siz = left_siz + 1 + right_siz;
tr[u].hash_value = tr[tr[u].l].hash_value * pw[right_siz + 1]
+ (ull)tr[u].val * pw[right_siz]
+ tr[tr[u].r].hash_value;
}
// 按排名分裂：x 保存前 k 个字符，y 保存剩余字符。
void split(int u, int k, int &x, int &y) {
if (u == 0) {
x = y = 0;
return;
}
if (tr[tr[u].l].siz >= k) {
y = u;
split(tr[u].l, k, x, tr[y].l);
push_up(y);
}
else {
x = u;
split(tr[u].r, k - tr[tr[u].l].siz - 1, tr[x].r, y);
push_up(x);
}
}
// 合并两段相邻的字符串。
int merge(int x, int y) {
if (x == 0 || y == 0) return x + y;
if (tr[x].fix > tr[y].fix) {
tr[x].r = merge(tr[x].r, y);
push_up(x);
return x;
}
else {
tr[y].l = merge(x, tr[y].l);
push_up(y);
return y;
}
}
// 取得子树 u 内第 l 到第 r 个字符的哈希，位置从 1 开始。
//
// 这里不使用 split 把区间切出来，而是只读地沿 Treap 查询。
// 好处是：一次 LCQ 要二分很多次；若每次查询都 split、merge，常数会较大。
//
// 当前子树的中序字符串可看成：
//
// 左子树字符串 + 当前字符 + 右子树字符串
//
// 我们把查询区间和这三段分别求交。完全被查询区间覆盖的子树，
// 可以直接使用该子树已经维护好的 hash_value，无须继续递归。
ull range_hash(int u, int l, int r) {
// 整棵子树都被取到：直接返回预处理好的整段哈希。
if (l == 1 && r == tr[u].siz) return tr[u].hash_value;
// 左子树占据位置 [1, left_siz]，当前字符的位置是 middle_pos。
int left_siz = tr[tr[u].l].siz;
int middle_pos = left_siz + 1;
ull ans = 0;
// 1. 查询区间与左子树有交集。
if (l <= left_siz) {
int part_l = l;
int part_r = min(r, left_siz);
// 先拼接左边这一段。若它长 len，则旧 ans 要左移 len 位：
// hash(ans + part) = hash(ans) * base^len + hash(part)。
ans = ans * pw[part_r - part_l + 1]
+ range_hash(tr[u].l, part_l, part_r);
}
// 2. 查询区间包含当前节点的字符。
if (l <= middle_pos && middle_pos <= r) {
ans = ans * base + tr[u].val;
}
// 3. 查询区间与右子树有交集。
// 右子树的内部编号从 1 开始，因此要减去 middle_pos。
if (r > middle_pos) {
int part_l = max(1, l - middle_pos);
int part_r = r - middle_pos;
// 最后把右边这一段接在 ans 后面，保持字符串从左到右的顺序。
ans = ans * pw[part_r - part_l + 1]
+ range_hash(tr[u].r, part_l, part_r);
}
// ans 按“左段 + 当前字符 + 右段”的顺序拼好，正是 [l, r] 的哈希。
return ans;
}
void insert_after(int pos, int val) {
int x, y;
split(root, pos, x, y);
root = merge(merge(x, new_node(val)), y);
}
// 找到第 pos 个节点，修改字符后沿递归路径更新哈希。
void change(int u, int pos, int val) {
int left_siz = tr[tr[u].l].siz;
if (pos <= left_siz) change(tr[u].l, pos, val);
else if (pos == left_siz + 1) tr[u].val = val;
else change(tr[u].r, pos - left_siz - 1, val);
push_up(u);
}
bool check(int x, int y, int len) {
if (len == 0) return true;
return range_hash(root, x, x + len - 1)
== range_hash(root, y, y + len - 1);
}
bool check_len(int len) {
return check(query_x, query_y, len);
}
// 由 rbook 的 first_true 模板改造而来：
// 在 [left, right] 中寻找第一个 check_len(len) 为假的长度。
// right 可以是虚拟失败位置，循环中不会用它调用 check_len。
int first_fail(int left, int right) {
while (left < right) {
int mid = (left + right) / 2;
if (check_len(mid)) left = mid + 1;
else right = mid;
}
return left;
}
void solve() {
string s;
cin >> s >> m;
pw[0] = 1;
int limit = (int)s.size() + m + 1;
for (int i = 1; i <= limit; i++) {
pw[i] = pw[i - 1] * base;
}
for (int i = 0; i < (int)s.size(); i++) {
root = merge(root, new_node(s[i] - 'a' + 1));
}
for (int i = 1; i <= m; i++) {
char op, ch;
int x, y;
cin >> op >> x;
if (op == 'I') {
cin >> ch;
insert_after(x, ch - 'a' + 1);
}
else if (op == 'R') {
cin >> ch;
change(root, x, ch - 'a' + 1);
}
else {
cin >> y;
int length = tr[root].siz;
if (x == y) {
cout << length - x + 1 << '\n';
continue;
}
query_x = x;
query_y = y;
int upper = min(length - x + 1, length - y + 1);
cout << first_fail(0, upper + 1) - 1 << '\n';
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}Python 同算法实现
下面的 main.py 与 C++ 正解使用相同的隐式 FHQ Treap、
import sys
sys.setrecursionlimit(1_000_000)
BASE = 233
MASK = (1 << 64) - 1
seed = 712367821
power = []
def next_priority():
"""xorshift64：给 FHQ Treap 生成随机优先级。"""
global seed
seed ^= (seed << 7) & MASK
seed ^= seed >> 9
return seed
class Node:
__slots__ = ("value", "priority", "size", "hash_value", "left", "right")
def __init__(self, value):
self.value = value
self.priority = next_priority()
self.size = 1
self.hash_value = value
self.left = None
self.right = None
def size(node):
return node.size if node is not None else 0
def hash_of(node):
return node.hash_value if node is not None else 0
def pull(node):
"""由“左子串 + 当前字符 + 右子串”更新长度和整段哈希。"""
left_size = size(node.left)
right_size = size(node.right)
node.size = left_size + 1 + right_size
node.hash_value = (
hash_of(node.left) * power[right_size + 1]
+ node.value * power[right_size]
+ hash_of(node.right)
) & MASK
def split(node, first_count):
"""按位置分裂：返回前 first_count 个字符和其余字符。"""
if node is None:
return None, None
if size(node.left) >= first_count:
left_tree, node.left = split(node.left, first_count)
pull(node)
return left_tree, node
node.right, right_tree = split(node.right, first_count - size(node.left) - 1)
pull(node)
return node, right_tree
def merge(left_tree, right_tree):
"""连接两个相邻的字符段。"""
if left_tree is None:
return right_tree
if right_tree is None:
return left_tree
if left_tree.priority < right_tree.priority:
left_tree.right = merge(left_tree.right, right_tree)
pull(left_tree)
return left_tree
right_tree.left = merge(left_tree, right_tree.left)
pull(right_tree)
return right_tree
def range_hash(node, left, right):
"""返回当前子树内第 left 到第 right 个字符的哈希（下标从 1 开始）。"""
if left == 1 and right == node.size:
return node.hash_value
left_size = size(node.left)
result = 0
if left <= left_size:
part_left = left
part_right = min(right, left_size)
part_hash = range_hash(node.left, part_left, part_right)
result = (result * power[part_right - part_left + 1] + part_hash) & MASK
middle_pos = left_size + 1
if left <= middle_pos <= right:
result = (result * BASE + node.value) & MASK
if right > middle_pos:
part_left = max(1, left - middle_pos)
part_right = right - middle_pos
part_hash = range_hash(node.right, part_left, part_right)
result = (result * power[part_right - part_left + 1] + part_hash) & MASK
return result
def insert_after(root, position, value):
"""在 position 后插入；position 为 0 时插在开头。"""
left_tree, right_tree = split(root, position)
return merge(merge(left_tree, Node(value)), right_tree)
def replace(root, position, value):
"""将第 position 个字符改为 value。"""
node = root
path = []
while True:
path.append(node)
left_size = size(node.left)
if position <= left_size:
node = node.left
elif position == left_size + 1:
node.value = value
break
else:
position -= left_size + 1
node = node.right
for node in reversed(path):
pull(node)
return root
def solve():
global power
readline = sys.stdin.buffer.readline
initial = readline().strip()
operation_count = int(readline())
operations = [readline().split() for _ in range(operation_count)]
# 最多每个操作都插入一个字符，预处理全部可能长度的 base 幂。
power = [1] * (len(initial) + operation_count + 2)
for i in range(1, len(power)):
power[i] = (power[i - 1] * BASE) & MASK
root = None
for char in initial:
root = merge(root, Node(char - 96))
answers = []
for operation in operations:
kind = operation[0]
if kind == b'I':
position = int(operation[1])
root = insert_after(root, position, operation[2][0] - 96)
elif kind == b'R':
position = int(operation[1])
root = replace(root, position, operation[2][0] - 96)
else:
x = int(operation[1])
y = int(operation[2])
length = root.size
if x == y:
answers.append(str(length - x + 1))
continue
upper = min(length - x + 1, length - y + 1)
low, high = 0, upper
# rbook 二分模板的“找第一个 true”在这里等价为：
# 对单调的“前 k 个相同”寻找最后一个 true。
while low < high:
middle = (low + high + 1) // 2
if range_hash(root, x, x + middle - 1) == range_hash(root, y, y + middle - 1):
low = middle
else:
high = middle - 1
answers.append(str(low))
sys.stdout.write("\n".join(answers))
if __name__ == "__main__":
solve()复杂度
设当前长度为
总结
静态字符串可用后缀数组把 LCQ 转为 height 的区间最小值；动态字符串则不维护后缀排序，而是把 LCQ 转为“最长相同前缀”的二分判定。隐式 FHQ Treap 维护字符顺序和区间哈希，正好支持插入、修改与子串比较。
同目录的 main.py 是相同算法的 Python 学习实现，brute.py 与 gen.py 仅用于小规模随机对拍；正式提交代码为 main.cpp。