重拾 DP（三）：DP 的线段树优化

__biu_biu_biu__ · 2026-07-20 10:39:13 · 算法·理论

前言

第一期地址：重拾 DP（一）：区间类 DP 和划分类 DP

第二期地址：重拾 DP（二）：字符串背景下的 DP

增加了一些 atcoder 和 CF 的例题喵。

内容主要包含线段树优化 DP。

线段树优化 DP

由于树状数组优化 DP 和线段树优化 DP 是子集关系，所以这里就不讲树状数组优化 DP 了。

线段树优化 DP 主要是在一类需要转移 \max\limits_{l_i\le j\le r_i},\min\limits_{l_i\le j\le r_i},\sum\limits_{l_i\le j\le r_i},\bigoplus\limits_{l_i\le j\le r_i} 等等区间类且支持两区间合并的转移。

其的修改一般是区间加减乘除或赋值，遇到区间取最值的时候，需要吉司机线段树。

时间复杂度一般是 O(\log) 的转移，下面我们举几道例题。

P6564 [POI 2007] 堆积木KLO

你有一个长度为 n 的序列 a，定义其的美丽度为 \sum [a_i=i]。你可以任意删除元素，求最终的美丽度的最大值。1\le n\le 10^5,1\le a_i\le 10^6。

考虑 dp_i 表示前 i 个删除若干元素且第 i 个元素是最后一个有贡献的位置时的最大美丽度。

则 dp_i=\max\limits_{1\le j<i\land 0<a_i-a_j<i-j}dp_j+1。

转换一下，可以得到两个限制条件：a_j<a_i 和 a_i-i<a_j-j，如果你直接转移是需要树套树的，很麻烦，所以我们考虑删掉一个限制条件，注意到 a_j<a_i 和 a_i-i<a_j-j 可以推出 j<i，所以可以不要 j<i 的情况，即不按顺序转移。

所以我们将 a 排序，然后从前往后枚举，这样就满足了 a_j<a_i 第一个条件，剩下的一个条件 j-a_j<i-a_i 使用树状数组或线段树优化即可，这两个条件可以推出 j<i，故不用额外限制。

细节有点多，但可以通过。

P9049 [PA 2021] Mopadulo

将长度为 n 的序列 A 划分成若干段，使得每一段的和模 10^9+7 都是偶数，求划分方案数。答案对 10^9+7 取模。1\le n\le 3\times 10^5。

考虑 dp_i 表示将前 i 个划分成若干满足条件的段的方案数，为了方便，我们记 f(l,r) 表示 \sum\limits_{l\le x\le r}A_x\bmod 10^9+7 的值。

有转移 dp_i=\sum\limits_{1\le j<i\land f(j+1,i)\bmod 2=0}dp_{j}。

这个转移用前缀和优化是 O(n^2) 的，考虑优化。

注意到 f(j+1,i) 的奇偶性满足：

• 如果 f(1,i)>f(1,j) 且 f(1,i) 与 f(1,j) 相同奇偶性，则 f(j+1,i) 是偶数。
• 如果 f(1,i)<f(1,j) 且 f(1,i) 与 f(1,j) 不相同奇偶（因为要加上 10^9+7 变成正数，奇偶会改变）则 f(j+1,i) 是偶数。

因此考虑对 f(1,i) 的奇偶性建两棵线段树，每次查询找相同奇偶性且值小于它的、和不同奇偶性且值大于它的，转移时区间求和单点赋值。时间复杂度 O(n\log V),V=10^9+7。

P11255 [GDKOI2023 普及组] 淋雨

有 n 个雨滴，每个雨滴 i 从 (x_i,y_i) 开始下落，每秒向下坠落 v_g 米，向右移动 v_w 米，有 q 个询问，每个询问给你一个 r，表示你起点在 (r,0)，每秒最多移动向左或右移动不超过 v_c 单位，求最多能接到多少雨滴。1\le n,q\le 10^5,1\le v_w,v_g,v_c,y_i\le 10^6,-10^6\le x_i,r\le 10^6。

有很多次询问显然不好做，我们先来考虑单个点的情况。

如果一个雨滴 (x_i,y_i) 可以被接到，那么当且仅当在 t_i=\frac{y_i}{v_g} 时间之前你就已经在 (p_i=x+v_w\times t_i,0) 等着了，由于你接到雨滴的时间一定是单调递增的，所以考虑按坠落到地上的时间排序。

考虑 dp_i 表示最后接到了第 i 个雨滴时之前最多接了多少个雨滴，则有转移 dp_i=\max\limits_{i<j\le n\land |p_i-p_j|\le v_c(t_i-t_j)} dp_j+1。

由于你一开始可能在一些很奇怪的点，不好转移，所以我们考虑在一开始站的位置加上雨滴 (r,0)，最后将贡献减去 1。

这样做是 O(n^2) 的，考虑优化。我们发现 |p_i-p_j| 不太好优化，考虑将绝对值拆开，变成 p_i-p_j(p_i>p_j) 和 p_j-p_i(p_j>p_i) 分开计算。

先来算 p_i-p_j\le v_c(t_i-t_j)，即 p_i-p_j\le \frac{y_iv_c}{v_g}-\frac{y_jv_c}{v_g}，化简得到 p_iv_g-y_iv_c\le p_jv_g-y_jv_c。

同理 p_j-p_i\le v_c(t_i-t_j)，即 p_j-p_i\le \frac{y_iv_c}{v_g}-\frac{y_jv_c}{v_g}，化简得到 p_jv_g+y_jv_c \le p_iv_g+y_iv_c。

但是如果你直接做的话是无法转移的，我们再次分析这两个条件，发现如果两个点 i,j 可以转移，其实两个条件都可以满足，也就是说两种拆分其实是可以合并为一种二维偏序，且时间的限制也隐含在了转移里面。

对于多个点的情况，我们其实只需要一次 DP 即可，我们可将所有的点一起加入转移，因为每个点的转移是互不影响的，时间复杂度 O((n+q)\log (n+q))。

AT_dp_w Intervals

给你 m 个条件 l_i,r_i,a_i，构造一个长度为 n 的 01 字符串 S，若 S_{l_i\sim r_i} 至少有一个是 1，则获得 a_i 的分数，求能获得的分数的最大值。n,m\le 2\times 10^5。

由于我们的贡献只跟 1 有关，因此考虑 dp_i 表示第 i 个字符染 1 的最大价值。但是这样转移的话会非常不好转移，所以我们钦定每次的区间贡献只在最右端点进行转移，则有 dp_i=\max dp_j+\sum\limits_{j< l_k\le i\le r_k} a_k，时间复杂度 O(n^2m)，考虑优化。

我们来分析一下这个 \sum a_k 的变化情况：

• 在 l_k=i 时，在 j\in [0,l_k-1] 加入贡献 a_k。
• 在 r_k=i 时，在 j\in [0,l_k-1] 减少贡献 a_k。

也就是说，我们的 \sum a_k 的转移是会随着 i 的变化进行有规律的变化，我们发现这个变化可以线段树区间加来修改，因此这个题的思路我们就很清晰了：用线段树去维护区间加和区间最值。

AT_arc073_d [ARC073F] Many Moves

你有两颗棋子，分别在 A 和 B，你有 q 次操作，每次将其中一个棋子移到 x_i，每移动一个棋子 1 距离需要花费 1 代价，求最少代价。1\le n,q\le 2\times 10^5,1\le A,B,x_i\le n。

考虑 dp_{i,j} 表示第 i 个操作后一个点在 x_i 另一个点在 j 的最小代价。

则有 dp_{i,j}=dp_{i-1,j}+|x_{i-1}-x_i|，还有 dp_{i,x_{i-1}}=\min dp_{i-1,k}+|k-x_i|，时间复杂度 O(n^3)，空间 O(n^2)，会超时。

考虑将 DP 滚动后，放到权值线段树上进行操作，这样第一个操作就是赋值了。

对于第二个操作，这里只是单点赋值 x，但需要找 [1,n] 的最值，对此我们考虑将绝对值拆开，将 [1,x] 的部分维护最值 dp_i-i+x，[x,n] 的部分维护最值 dp_i+i-x，然后求 [1,n] 的最值即可。

CF2150C Limited Edition Shop

有 n 件物品，第 i 件的价值是 v_i，A 的购物顺序是 a_1,a_2,\dots a_n，B 是 b_1,b_2,\dots b_n，每次可以让任意一个人去购买自己最想购买的东西。求 A 得到的物品的价值之和最大是多少。1\le n\le 2\times 10^5。

考虑 dp_{i,j} 表示 A 决策到了自己想要买的第 i 个，B 决策到了自己想要买的第 j 个时 A 可以获得的物品价值最大为多少。

则有 dp_{i,j}=dp_{i-1,j}+v_{a_i}，但这里需要考虑 a_i 是否在状态 dp_{i-1,j} 时已经被 B 购买过了，所以 dp_{i,j}=dp_{i-1,j}(p_{a_i}\le j)，p_x 表示物品 x 在 B 的购物清单的第 p_x 个位置。

这个物品还可以给 B 买，即 dp_{i,\max(p_{a_i}, j)}=dp_{i-1,j}，时间复杂度 O(n^2)，空间复杂度 O(n^2)，考虑优化。

首先可以滚动一维，变成空间复杂度 O(n)。

这个 \max(p_{a_i},j) 很不好处理，考虑拆开，即为 dp_{i,p_{a_i}}=dp_{i-1,j}(p_{a_i}>j),dp_{i,j}=dp_{i-1,j}(p_{a_i}<j)。

此时有 dp_{p_{a_i}}=\max\limits_{1\le j<p_{a_i}} dp_j，对于 j\in [0,p_{a_i})，有转移 dp_j=dp_j+v_{a_i}，对于 j\in (p_{a_i},n]，有转移 dp_j=dp_j。

需要支持区间加，区间取最值，区间赋值，使用线段树维护即可。

CF115E Linear Kingdom Races

你有 n 个初始是白色的点，将第 i 个点染成黑色需要 a_i 的代价，有 m 个奖励，如果区间 [l_i,r_i] 所有的点全部被染成黑色，则获得 p_i 的价值，求能获得的最大价值。1\le n,m\le 2\times 10^5。

考虑 dp_i 表示第 i 个点染成黑色时能获得的最大价值。

我们考虑划分一个白色段，即 dp_i=\max\limits_{1\le j<i}dp_{j-1}+\sum\limits_{j<l_k\land r_k=i}p_j-\sum\limits_{j<k\le i}a_k，时间复杂度 O(n^2m)，考虑优化。

考虑对下标 [1,n] 建线段树。我们考虑在 i 固定时，对于每一个奖励 [l_k,i]，将 j\in [0,l_k) 的位置区间加 p_k，这样的话可以处理 \sum\limits_{j<l_k\land r_k=i}p_j 这个部分的值；然后考虑将 \sum\limits_{j<k\le i}a_k 拆成 \sum\limits_{1\le k\le i}a_k-\sum\limits_{1\le k\le j}a_k，然后将线段树上第 i 个节点加上 \sum a_k，然后在统计答案的时候减去 \sum\limits_{1\le k\le i}a_k 的价值即可。

P11491 [BalticOI 2023] Tycho

你要从数轴上的点 0\to b，每秒只能向前走一步或者停留，现在数轴上有 n 个点 a_1,a_2,\dots a_n，给定 p，如果在 kp 秒内你不在 0,b,a_1,a_2\dots a_n 这 n+2 个点中的任意一个，则你需要支付 d 的代价。求代价与到达 b 的时间之和的最小值。0\le n\le 10^5,1\le p<b\le 10^{12},0\le d\le 10^6,n<b。