如何将线段树优化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)\)。当 \(i\) 从 \(1\) 到 \(n\) 枚举时： 将区间 \([pre[a_i], i-1]\) 加 \(1\)（表示这些 \(t\) 对应的 \(\text{cost}\) 增加）。 查询区间 \([j-1, i-1]\) 的最大值，即为 \(dp[i][j]\)。 更新 \(pre[a_i] = i\)。 这样在计算第 \(j\) 层时，我们需要事先用 \(dp[*][j-1]\) 初始化线段树。\(dp[0][0] = 0\)，其余为负无穷。每次计算完 \(dp[i][j]\) 后，\(dp[i][j]\) 会被用于下一层 \(j+1\) 的初始化，但下一层的线段树需要重新建树（基于新的 \(j\)）。 复杂度 \(O(k n \log n)\)，空间 \(O(k n)\) 但可以滚动优化，不过 \(n\) 较大时通常需要开 \(O(nk)\)，这里 \(k \le 50\)，可以接受。 代码 戳我喵~ #include <bits/stdc++.h> #define re read() #define wr(n) write(n) #define sp putchar(' ') #define endl puts("") #define int long long const int N = 3e4 + 5010, INF = 1e9; const double ecnts = 1e-6; using namespace std; using lint = long long; using ulint = unsigned long long; using pii = pair<int, int>; int read() {...} void write(int x) {...} const int mod = 1e9 + 7; int n, K; int dp[N][60]; // dp[i][j] #define ls p << 1 #define rs p << 1 | 1 struct Tree { int l, r; int val, lazy; }tree[N << 2]; void pushup(int p) {tree[p].val = max(tree[ls].val, tree[rs].val);} void pushdown(int p) { if (tree[p].lazy) { tree[ls].val += tree[p].lazy, tree[rs].val += tree[p].lazy; tree[ls].lazy += tree[p].lazy, tree[rs].lazy += tree[p].lazy; tree[p].lazy = 0; } } // 用第 line 层的 dp 值建树，即 dp[l][line] 作为叶子 t = l 的初值 void build(int p, int l, int r, int line) { tree[p].l = l, tree[p].r = r; tree[p].val = dp[l][line], tree[p].lazy = 0; if (l == r) return ; int mid = l + r >> 1; build(ls, l, mid, line), build(rs, mid + 1, r, line); pushup(p); } // 区间加 k void update(int p, int l, int r, int k) { if (l <= tree[p].l && tree[p].r <= r) { tree[p].val += k; tree[p].lazy += k; return ; } pushdown(p); int mid = tree[p].l + tree[p].r >> 1; if (l <= mid) update(ls, l, r, k); if (r > mid) update(rs, l, r, k); pushup(p); } // 区间查询最大值 int query(int p, int l, int r) { if (l <= tree[p].l && tree[p].r <= r) return tree[p].val; pushdown(p); int ans = 0; int mid = tree[p].l + tree[p].r >> 1; if (l <= mid) ans = max(ans, query(ls, l, r)); if (r > mid) ans = max(ans, query(rs, l, r)); return ans; } int a[N], pre[N]; signed main() { int n = re, k = re; for (int i = 1; i <= n; i++) a[i] = re; for (int j = 1; j <= k; j++) { // 用 dp[0..n][j-1] 建树，注意线段树节点 t 对应 dp[t][j-1] build(1, 0, n, j - 1); // 初始化 pre 数组，记录每个值在当前层扫描过程中的上一次出现位置 for (int i = 1; i <= n; i++) pre[a[i]] = 0; for (int i = 1; i <= n; i++) { // 将区间 [pre[a[i]], i-1] 加 1，表示 cost 增加 update(1, pre[a[i]], i - 1, 1); // 查询 [j-1, i-1] 的最大值作为 dp[i][j] dp[i][j] = query(1, j - 1, i - 1); pre[a[i]] = i; // 更新上一次出现位置 } } wr(dp[n][k]), endl; }