[动态规划] 离线区间 LCS

Felix72 · 2025-09-30 18:18:32 · 算法·理论

概括

有字符串 s, t 长度为 n, m，现有 k 组无特殊性质的区间询问，则该离线区间 \text{LCS} 问题可以在 O((k + n\log n)m) 时间内解决。

正文

某天，桑格莉娅在又一次被三跑之后很红温，她找到同为版本角色的麦克莫顿，询问他怎样提升追击能力。

麦克略加思索，说到：“多看职业联赛。”

桑格莉娅觉得好有道理啊，于是找了一份 \text{IVL} 赛场上的的歌剧演员集锦拿出来看。看着看着她发现了自己的问题：庄园里很多地方是她可以用技能直接一步跳过去的，而她却不太会估计距离，导致多走了很多弯路。

比如下面的这个图，假设右下角有个人在修机子，桑格莉娅要从左上角赶到右下角，她本可以走红色的最短路，但是由于对地图不熟悉，她最终走的可能是蓝色的较劣路径。

了解这一点后，她开始研究最短路径怎么计算。一旁凑热闹的艾维告诉她，这个问题可以用 \text{DP} 求解，设 f_{i, j} 表示走到当前格子时经过的最多斜边数量就可以啦。

桑格莉娅表示你说的对，但是我想要一个子矩阵查询的算法，O(n^2\log n) 的那种。

众人犯了难。询问的自由度太高了，让人不知从何下手。但是很快猫猫教会的安表示，自己教派有一种叫做猫树的宗教仪式，大概就是把一个问题分治，每次解决跨过中点的询问，剩下的再递归，这样，只要保证问题的两半可以合并，那就能用一个 \log n 直接让问题减少一个维度，太赚了。

于是现在需要解决的问题就变成了这样：从点 (1, i) 到 (k, j)，最多走几条斜边？可是这个问题还是有三个维度，最好能用数据结构或者性质再去掉一维。

经过漫长的手玩，观察力惊人的桑格莉娅观察到了一个性质！

她说：“当 i, j, k 确定时，可以设我经过的斜边数量最多为 w。显然当 k 增大 1 时，w 有可能加一，也有可能不变。但是我发现，对于一个固定的 j 来说，i 越小，w 越可能加一。”

“为什么呢？如果 (1, i) \to (k, j) 的答案可以加一的话，那么一定存在一条像这样的蓝色路径，使得我可以走 k \to k + 1 行的一条斜边。那么这个问题可以分两种情况讨论。”

“如果 (1, i - 1) \to (k, j) 的答案本就等于 (1, i) \to (k, j) 的答案，那么可以先一步走到 (1, i) 再走蓝色路径；”

“另一种情况是 (1, i - 1) \to (k, j) 的答案比 (1, i) \to (k, j) 的答案大 1。但是你看，这 (1, i) \to (k, j) 的最优路径不可能和蓝色路径交错过去，不然交错之后的后半段直接走蓝色就可以了对不对？”

“因此我们可以知道，k \to k + 1 时对于固定的 j，有一个前缀的 i 会满足 (1, i) \to (k, j) 的答案加一，我们把这个前缀的右端点记为 q(k + 1, j)。”

“不仅如此啊，j \to j + 1 时对于固定的 k，有一个后缀的 i 会满足 (1, i) \to (k, j) 的答案加一，剩下的不变，不妨记这个后缀的左端点为 p(k, j + 1)。证明也可以用这个格子图。”

艾维看了看感觉挺对的。“但是我们还是不能回答 (1, i) \to (k, j) 的答案啊？除非把 p 和 q 都算出来 \dots 欸欸欸好像真能算啊？”

桑格莉娅和艾维发现，p 和 q 好像能递推！具体是怎么个事呢？她们举了个例子帮你理解：

当 j, k 固定时，ans(i, j, k) 是一个以 i 作为下标的数列。设其为 a_1, a_2, \dots, a_n。那么根据刚才研究的前后缀理论，有以下三种情况可以讨论。为了便于你理解，设 n = 7：

Case 1

假设 (j - 1, k - 1) \to (j, k) 没有斜边，且 q(j - 1, k) < p(j, k - 1)：