如何将线段树优化DP成？

不会线段树的，出门左转oi-wiki 正如标题，利用了线段树的区间查询的特点，可以将区间查询优化到 \(log\) 级别。 例题：P3970 [TJOI2014] 上升子序列 总感觉这道题有点似曾相识。。。 解法 如果是只要下标不同，就很好做了。 先想一下不管如果两个上升子序列相同，那么只需要计算一次这个条件时的做法。 当前这个数可以先查询比它小的数的总个数，那么再加上它自己就是它的贡献了。 可是有了如果两个上升子序列相同，那么只需要计算一次条件，怎么办呢？ 我们可以用一个 map 去存它上一次的贡献，如果相同就不管它。 如果不同，那么将两次贡献的差值加入线段树内即可，还要更新为新的贡献值。 提示：如果不想打权值线段树，就使用离散化。 代码 戳我喵~(这是树状数组写法，可以替换成线段树) const int mod = 1e9 + 7; //不要忘记了mod int n = re; int a[N], b[N]; lint dp[N]; lint tree[N << 2]; #define lowbit(x) x & (-x) void update_add(int x, lint add) { //对应你线段树的区间修改 for (; x <= n; x += lowbit(x)) tree[x] += add; } lint query(int x) { //对应你的线段树区间查询 lint ans = 0; for (; x; x -= lowbit(x)) ans += tree[x]; return ans; } signed main() { for (int i = 1; i <= n; i++) b[i] = a[i] = re; sort(b + 1, b + 1 + n); //离散化 int m = unique(b + 1, b + 1 + n) - b - 1; for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + m, a[i]) - b; for (int i = 1; i <= n; i++) { lint x = (query(a[i] - 1) % mod + 1) % mod; //查询比自己小的值的个数 if (x != dp[a[i]]) update_add(a[i], (x - dp[a[i]] + mod) % mod), dp[a[i]] = x; } wr((query(m) % mod - m + mod) % mod); } T2:CF833B The Bakery 解法 这是一道经典的 DP 优化问题。朴素 DP 为： 设 \(dp[i][j]\) 表示将前 \(i\) 个元素分成 \(j\) 段的最大总价值。 转移：\(dp[i][j] = \max_{t = j-1}^{i-1} \big( dp[t][j-1] + \text{cost}(t+1, i) \big)\)，其中 \(\text{cost}(l, r)\) 表示区间 \([l, r]\) 中不同数字的个数。 直接计算复杂度 \(O(k n^2)\)，无法通过。需要优化。 线段树优化 观察到当 \(i\) 向右移动一位时，所有以 \(t\) 为上一段结束位置的状态值 \(dp[t][j-1] + \text{cost}(t+1, i)\) 中，只有一部分需要更新：因为新加入的元素 \(a_i\) 会对所有 \(t < i\) 且 \(a_i\) 在 \((t+1, i-1]\) 中未出现过的区间贡献加 1。具体来说，设 \(pre[x]\) 表示值 \(x\) 上一次出现的位置（在扫描 \(i\) 的过程中动态维护），则当 \(i\) 从 \(i-1\) 变成 \(i\) 时，对于所有 \(t \in [pre[a_i], i-1]\)，\(\text{cost}(t+1, i) = \text{cost}(t+1, i-1) + 1\)（因为 \(a_i\) 在 \([t+1, i-1]\) 中未出现过）；对于 \(t < pre[a_i]\)，\(\text{cost}\) 不变。 因此我们可以为每个 \(j\) 维护一棵线段树，叶子节点 \(t\) 存储值 \(dp[t][j-1] + \text{cost}(t+1, \text{当前} i)\)。