P15532这题名字叫《好想大声说爱你》要不是在MYCOI R1的题单里看到我差点以为是什么字符串模拟入门的浪漫签到题。点进去之后才发现核心问题其实是一个很经典的区间子序列判定给定一个字符串每次问某个区间内能不能按顺序挑出几个字符组成指定模式串。我一开始也想写暴力扫描看了眼数据范围之后果断放弃最后用线段树维护状态矩阵的方式过了。这篇文章就把我的完整推导、代码实现和踩过的坑都写出来希望能给同样被这题卡住的人一点参考。这道题的适用范围其实不窄OIer、ACM选手、甚至准备面试的时候被问到“区间内是否存在某子序列”这类问题都能直接用上。我会先从最朴素的暴力思路讲起再一步步走到线段树状态矩阵的写法保证就算你之前没怎么接触过这类数据结构也能顺着思路把代码写出来。1. 题面翻译与两条暴力路线的瓶颈1.1 把“大声说爱你”翻译成标准题意题目的大意我整理成下面的形式给定一个长度为 n 的字符串 S只包含小写字母。有 q 次询问每次给一个区间 [l, r]问 S[l..r] 这个子串里能不能通过删除若干字符、但不改变剩余字符的相对顺序得到一个等于 love 的字符串。如果可以输出 Yes否则输出 No。这个其实就是标准的“子序列匹配”问题只不过匹配的目标串是固定的 love。为什么标题叫《好想大声说爱你》因为love嘛四个字母正好对应一段告白出题人把一个看似文艺的场景抽象成了字符串题这在竞赛里太常见了。如果原题的数据范围比较小比如 n 和 q 都在几千以内那暴力其实就够了。但这类题既然挂在线段树上数据范围基本不会太友好。我按常规题面来假设 n 和 q 都是 1e5 级别那么任何单次询问 O(n) 的做法都会直接超时。1.2 暴力一每个询问从 l 到 r 扫一遍最直观的想法是这样对于一个询问 [l, r]我维护一个指针 idx 初始指向 love 的第一个字符 l。然后从 l 到 r 扫描 S如果当前字符正好等于 pat[idx]pat 是 love下标从 1 开始就 idx直到 idx 5 说明四个字符都找到了。这个思路正确性没问题但每次询问的代价是 O(n)总复杂度 O(nq)。当 n q 1e5 时1e10 的运算量在任何竞赛环境下都是不可能跑完的。所以这条路走到头了必须想办法预处理。我见过不少新手在这里会试图加一些优化比如先判断区间长度够不够 4或者在每个询问里先用前缀和看看每个字符出现次数够不够。但这些优化在最坏情况下都不改变 O(nq) 的本质因为字符出现的顺序才是关键仅仅统计数量解决不了顺序问题。1.3 暴力二预处理 next 数组只适合静态串再进一步想单次询问真正消耗时间的地方是在区间里反复扫描找下一个需要的字符。如果我能提前知道“在某个位置后面下一个指定字符出现在哪里”那一次匹配love需要找 4 次字符不就变成 O(4) 了吗这其实就是子序列自动机也叫 next 数组的思路。预处理 nxt[i][c] 表示在位置 i 之后严格大于 i第一次出现字符 c 的位置。然后对于区间 [l, r]我从 l-1 出发依次跳向 l、o、v、e每次跳到下一个位置最后看看跳到的位置是否不超过 r。这个做法对于静态字符串非常优秀预处理 O(26n)每次询问 O(4)总复杂度 O(26n 4q)轻松通过。那为什么还需要线段树因为一旦题目加上单点修改比如把 S 的某个位置的字符改掉nxt 数组就需要大范围重构最坏情况下一次修改就要 O(26n)完全没法接受。如果你确定这道题没有修改操作其实用 next 数组就够了甚至比线段树好写很多。但 P15532 这题的价值就在于让我把线段树的状态矩阵写法完整跑了一遍所以接下来我重点讲支持修改的做法。2. “最早结束位置”为什么是贪心最优解2.1 为什么“越早结束越好”在进入线段树之前有一个核心思想必须先想清楚当我们从左往右匹配一个模式串时如果存在多种方式匹配到同一个状态比如已经匹配好了 lo那么“最后一个被用到的字符的位置”越小越好。道理很简单后续还剩下 ve 两个字符要匹配而区间向右延伸的范围是固定的。如果前面的匹配结束得越早留给我继续匹配后面字符的可用区间就越大反之如果前面某个字符用得太靠右可能后面 v 和 e 的位置虽然存在却被挤出了当前询问区间。这个逻辑可以严格证明假设从状态 x 出发有两种方式都到达状态 y且结束位置分别是 p1 和 p2满足 p1 p2。那么从状态 y 继续匹配后续字符时任何在位置 p2 之后能完成的匹配在 p1 之后也同样能完成因为 p1 给了你更大的空间。所以无论之后要匹配什么选择结束位置更小的方案永远不会比更大的方案差。这就是整个线段树状态设计的基石。我们在线段树每个节点里存的所有“最短结束位置”本质上都是在做这个贪心决策。2.2 一次询问的最优走法站在一次询问的角度贪心匹配的过程是这样的初始状态是“已经匹配了 0 个字符”从 l-1 位置开始。先找第一个 l 出现的最早位置 p1然后从 p1 开始找下一个 o 的最早位置 p2依次类推。每次找“下一个指定字符的最早位置”其实就是在多个可行选择中挑结束位置最小的一种。假设我在找 o区间里出现了多个 o我选最靠左的那个。你可能会担心选最靠左的 o会不会导致后面 v 找不到不会。因为如果最靠左的 o 之后的可用区间里都找不到 v那换成更靠右的 o可用区间只会更短更不可能找到。所以“最早位置”永远是最优选择。这个思想反映到线段树上就是每个节点只用维护最小的结束位置不需要维护所有可达方案。2.3 next 数组与子序列自动机的关系这里顺便说清楚 next 数组和子序列自动机的关系nxt[i][c] 其实就是在点 i 处遇到字符 c 时应该转移到的下一个节点。对每个位置 i有 26 条出边所以它本质上是一个 DFA。每次询问就是在 DFA 上根据区间内的字符序列走看能不能在限定区间内走到接受状态。线段树的做法则是把这个 DFA 的信息按区间分块存储通过合并区间的转移关系来快速回答询问。两者底层逻辑一致但线段树版本天然支持修改因为修改一个点只需要更新从叶子到根的一条链。3. 线段树节点里的状态矩阵定义与合并规则3.1 mat[x][y] 到底存什么这一步是整个做法的灵魂也是最容易绕晕的地方。我定义每个线段树节点维护一个矩阵 mat大小为 (M1) * (M1)其中 M 是模式串 love 的长度也就是 4。下标从 0 到 M 分别代表“已经匹配了模式串前 i 个字符”的状态。关键定义来了对于 x ymat[x][y] 表示在这个节点对应的区间内部从“已经匹配好了前 x 个字符”的状态出发允许跳过任意字符并按顺序取字符至少把状态推进到“已经匹配好了前 y 个字符”在这个过程中最后一个被用到的字符在原串中的下标是多少。如果无法做到值为 INF。举个例子。假设模式串是 love某个节点对应的区间是位置 3 到 6里面的字符刚好是 l、o、v、e。那么mat[0][1] 3因为从空状态出发用位置 3 的 l就能推进到状态 1mat[0][2] 4因为依次用位置 3 的 l 和位置 4 的 o最后用到的字符在位置 4mat[1][4] 6因为从已经匹配了 l 的状态出发用位置 4、5、6 的 o、v、e最后停在位置 6mat[0][4] 6表示完整匹配 love最后一个字符在位置 6。特别注意当 x y 时表示不需要用任何字符就能保持原状态。这时我规定 mat[x][x] 等于“区间左端点 - 1”代表一个空操作匹配还没有真正消耗区间里的字符。3.2 叶子节点的构造规则对于只有一个字符的叶子节点构造规则非常简单。假设叶子节点对应原串位置 pos字符是 c。第一步先把所有 mat 值初始化为 INF。第二步对于每个状态 x0 到 M设置 mat[x][x] pos - 1表示空匹配。第三步如果 x M并且 pat[x 1] c说明当前这个字符 c 可以让状态从 x 推进到 x 1于是设置 mat[x][x 1] pos。这里有一点需要注意模式串中如果出现重复字符比如模式串是 aba那么一个叶子节点上的字符 a 同时满足 x 0 和 x 1 的情况因为 pat[1] a 且 pat[2] a。我的代码里是用一个循环枚举所有 x每个满足条件的 x 都会单独设置所以这种情况天然被覆盖了。3.3 合并规则为什么右边决定结束位置现在是最关键的部分怎么把左孩子和右孩子的信息合并成当前节点的信息。假设左孩子区间是 [L, mid]右孩子区间是 [mid 1, R]。我要计算当前节点的 res.mat[x][y]表示从状态 x 出发在整个 [L, R] 区间内推进到状态 y 的最早结束位置。这个目标路径只有两种可能第一种全程都在左孩子区间内完成也就是没有用到右孩子里的任何字符。这种情况的结果直接取左孩子的 mat[x][y]。第二种在左孩子区间内推进到了某个中间状态 z然后右孩子从状态 z 出发继续推进到最终状态 y。合并时我枚举这个中间状态 z。关键在于右孩子的所有位置都在左孩子所有位置的右边所以一旦路径跨过了中线最终被用到的最后一个字符一定在右孩子区间内。因此整个合并结果的结束位置就是右孩子从状态 z 推进到状态 y 的结束位置即右孩子的 mat[z][y]而不需要关心左孩子那一段到底在哪里结束。只要左孩子的 mat[x][z] 不是 INF说明左孩子确实能到达状态 z并且右孩子的 mat[z][y] 不是 INF说明右孩子能接上那么整体可达。对多个 z 取最小值即可。用公式表达就是res[x][y] min( left[x][y], min_{z from x to y, if left[x][z] INF and right[z][y] INF} right[z][y] )为什么 z 的范围是 x 到 y因为状态只会前进不会后退左孩子从 x 推进到的中间状态 z 不可能小于 x也不可能大于最终状态 y。这个范围限制可以省掉不少无效枚举。合并的代码看起来就是三层循环但每层最多 M1 次M 是 4所以完全不怕枚举。4. 完整实现建树、单点修改、区间查询4.1 代码设计的几个前置约定在写代码之前我先把所有约定说清楚避免你看代码之后产生混乱。模式串用字符数组 pat 存下标从 1 开始所以 pat[1] lpat[2] opat[3] vpat[4] e。M 是 4。原串 S 也是 1-based即下标从 1 到 n 存字符。INF 用一个足够大的数我习惯用 0x3f3f3f3f方便 memset。叶子节点里 mat[x][x] pos - 1这个值可能是 0当 pos 1 时但没关系它只表示空匹配不会和真实字符位置混淆。查询时我把答案累积到一个 Node 变量 ans 里初始时让 ans.mat[i][i] l - 1表示从区间左边的虚空位置开始还没有消耗任何字符。4.2 完整 C 实现#include bits/stdc.h using namespace std; const int MAXN 100005; const int M 4; // love 的长度 const int INF 0x3f3f3f3f; char pat[M 1] love; // 下标 1..M char s[MAXN]; int n, q; struct Node { int mat[M 1][M 1]; void clear() { memset(mat, 0x3f, sizeof(mat)); } } tree[MAXN * 4]; Node mergeNode(const Node A, const Node B) { Node C; C.clear(); for (int x 0; x M; x) { for (int y x; y M; y) { // 整个推进过程都在左区间 A 内完成 if (A.mat[x][y] INF) { C.mat[x][y] min(C.mat[x][y], A.mat[x][y]); } // 在 A 内推进到中间状态 z再由 B 继续推进到 y for (int z x; z y; z) { if (A.mat[x][z] INF B.mat[z][y] INF) { C.mat[x][y] min(C.mat[x][y], B.mat[z][y]); } } } } return C; } void build(int p, int l, int r) { if (l r) { tree[p].clear(); for (int x 0; x M; x) { // 空匹配不需要字符结束位置看作左端点前一位 tree[p].mat[x][x] l - 1; // 当前字符如果能推进状态 x - x1 if (x M pat[x 1] s[l]) { tree[p].mat[x][x 1] l; } } return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); tree[p] mergeNode(tree[p 1], tree[p 1 | 1]); } void update(int p, int l, int r, int pos) { if (l r) { tree[p].clear(); for (int x 0; x M; x) { tree[p].mat[x][x] l - 1; if (x M pat[x 1] s[l]) { tree[p].mat[x][x 1] l; } } return; } int mid (l r) 1; if (pos mid) { update(p 1, l, mid, pos); } else { update(p 1 | 1, mid 1, r, pos); } tree[p] mergeNode(tree[p 1], tree[p 1 | 1]); } void query(int p, int l, int r, int ql, int qr, Node ans) { if (ql l r qr) { ans mergeNode(ans, tree[p]); return; } int mid (l r) 1; if (ql mid) { query(p 1, l, mid, ql, qr, ans); } if (qr mid) { query(p 1 | 1, mid 1, r, ql, qr, ans); } } int main() { scanf(%d%d, n, q); scanf(%s, s 1); build(1, 1, n); while (q--) { int op; scanf(%d, op); if (op 1) { int pos; char c; scanf(%d %c, pos, c); s[pos] c; update(1, 1, n, pos); } else { int l, r; scanf(%d%d, l, r); Node ans; ans.clear(); for (int i 0; i M; i) { ans.mat[i][i] l - 1; } query(1, 1, n, l, r, ans); if (ans.mat[0][M] INF) { puts(Yes); } else { puts(No); } } } return 0; }4.3 查询初始状态的坑我在第一次写查询函数的时候犯了一个比较隐蔽的错误初始化 ans 的时候我把所有 ans.mat[i][i] 都设置成了 0。当时想的是最开始的空匹配位置当然是 0。但这个值用在不同的查询区间里是有问题的。比如询问 [l, r]如果 l 不是 1那么用位置 0 之前的空匹配去和一个覆盖 [l, r] 的线段树节点合并合并逻辑本身还是能工作的但 mat[i][i] 这个“空匹配结束位置”会被后续合并当成一个可参考的最小值虽然最终不会影响 mat[0][M] 的实际匹配结果但语义上不够严谨。后来我把 ans.mat[i][i] 改成 l - 1才彻底想通了这件事空匹配的位置本来就应该是查询区间左端点的前一个位置。这样所有空操作的坐标都跟着当前查询区间走合并出来的结果在逻辑上才是自洽的。这个细节如果不注意在做一些退化数据的时候可能产生奇怪的判断所以特别提醒一下。5. 复杂度、正确性验证与两个容易翻车的细节5.1 复杂度结论整个数据结构的复杂度可以分成三块看。建树时每个叶子节点构造是 O(1) 级别的枚举M 4每个内部节点做一次 mergeNode 操作。mergeNode 的三层循环枚举 x、y、z每个维度都是 M1 5所以一次合并大约 125 次操作。总建树复杂度 O(125n)常数很小。单点修改时从叶子到根只有一条链深度 O(log n)每层做一次合并复杂度 O(M^3 log n)。区间查询时线段树最多访问 O(log n) 个被完全覆盖的节点每访问一个节点做一次合并所以查询复杂度也是 O(M^3 log n)。再加上初始 ans 的构造 O(M)基本可以忽略。对于 n q 1e5M 4 的情况这个复杂度非常轻松常数小得可以忽略不计。5.2 手工跑一个小样例为了验证这套状态矩阵不是纸面功夫我手算一个简单的例子。S iloveyou下标从 1 开始1 i2 l3 o4 v5 e6 y7 o8 u。询问区间 [2, 5]也就是子串 love。我希望答案是 Yes。手动构造叶子位置 2 是 lmat[0][1] 2mat[x][x] 1。位置 3 是 omat[1][2] 3。位置 4 是 vmat[2][3] 4。位置 5 是 emat[3][4] 5。合并前四个叶子后会存在一条状态链 0 - 1 - 2 - 3 - 4最终 mat[0][4] 5。非 INF所以输出 Yes。再看询问区间 [3, 5]也就是 ove里面没有 l。叶子 4 和 5 只能从状态 2、3 往后推没有任何节点能把状态 0 推到状态 1。合并之后 mat[0][1]、mat[0][2]、mat[0][3]、mat[0][4] 全是 INF只有 mat[0][0] 是 2空匹配。所以 ans.mat[0][4] INF输出 No。这个例子算完我对自己的实现就有信心了。5.3 易错点空匹配与 INF 的区分这套代码里有两个容易混淆的概念我单独拿出来说。第一个是“空匹配”的位置。叶子节点里 mat[x][x] l - 1这个值看起来像是一个真实位置但它只是虚拟的起点表示“在这个区间开始之前就已经处于状态 x”。它只用于状态保持不表示实际用到了哪个字符。所以在判断最终答案的时候不能只检查 ans.mat[0][M] 是不是 l - 1 这类值而要看它是不是 INF。一旦 mat[0][M] 非 INF说明真的完成了一次从状态 0 到状态 M 的推进这个值是最后一个被用到字符的位置一定大于等于 l。第二个容易翻车的点是枚举范围。我在 mergeNode 里用了 z from x to y这个范围是严格的状态单调性约束。如果你偷懒写成 z from 0 to M结果不会错但会多做很多无效判断。更重要的是如果模式串长度变大比如变成了 50那 51 的三层循环就已经是 13 万级别能省一点是一点。所以 z 的范围最好按照状态单调性收紧。6. 这类题的变体与可复用的做题思路6.1 模式串长度不是 4 怎么办这道题模式串是固定的 love所以 M 4。但如果你遇到模式串长度为 10 甚至 20 的版本这套矩阵做法会遇到一个问题合并复杂度 O(M^3 log n) 会随着 M 增长变得不可接受。我实话说模式串一旦超过 10直接的矩阵合并就有点悬了M 20 的时候 8000 次内层操作乘上 log n 就很吃力。这时候有两个替代方案。第一种如果题目没有修改操作老老实实用 next 数组的子序列自动机单次询问 O(M)预处理 O(26n)这才是静态区间的正解。第二种如果题目强制修改可以考虑用 bitset 优化状态转移或者用分块 预处理小块转移矩阵把合并复杂度从 O(M^3) 降到接近 O(M^2 / 64)。但这就已经进入比较偏的优化领域了竞赛里出现频率不高。所以个人建议看到 M 很小比如 1 到 4直接用线段树矩阵M 中等评估修改频率和查询频率M 很大优先找静态做法或其他性质。6.2 只问最长可匹配前缀的做法有时候题目会从“能不能匹配完整模式串”变成“最长能匹配到模式串的前几位”。这个改法其实更简单。在得到了查询区间的 ans 矩阵之后我不需要检查 ans.mat[0][M]而是从大到小枚举一个状态 p看 ans.mat[0][p] 是不是 INF。第一个非 INF 的 p 就是最长可匹配前缀长度。这个思路在面试题里很有用比如“给定一个文本串在某个子区间内最多能匹配上 pattern 的前多少个字符”。用这套线段树矩阵答案是现成的。6.3 这道题留给我的经验最后说说我做题的具体体会。P15532 这题让我深刻意识到一个问题字符串题不一定非要用字符串算法尤其是“区间查询 区间合并”的味道出来之后线段树几乎是本能反应。关键在于怎么把“匹配进行到哪一步”压缩成一个可合并的状态。“已经匹配了模式串前 i 个字符”就是一个非常自然的状态而两个区间合并时只需要考虑左边区间把状态推进到哪个中间状态、右边区间能否接着推进。只要抓住了这个本质矩阵里存的是什么就一目了然了。如果你在考场上一时想不起线段树矩阵的合并细节我建议你先把“状态机”这三个字写在草稿纸上再写下状态 x 表示“前缀匹配长度”然后从叶子节点开始推。这种方式能帮你避免直接把左孩子和右孩子的 mat 相加这类常见错误。这题之后我又拿这套模板去练了好几个类似的区间子序列问题稳定性和正确性都很好。如果你也在刷字符串数据结构题强烈建议把这道题吃透它背后代表了一整类“区间匹配状态合并”的题目值得反复写几遍。