不会线段树的，出门左转oi-wiki
正如标题，利用了线段树的区间查询的特点，可以将区间查询优化到 \(log\) 级别。
例题：P3970 [TJOI2014] 上升子序列
总感觉这道题有点似曾相识。。。
解法
如果是只要下标不同，就很好做了。
先想一下不管如果两个上升子序列相同，那么只需要计算一次这个条件时的做法。
当前这个数可以先查询比它小的数的总个数，那么再加上它自己就是它的贡献了。
可是有了如果两个上升子序列相同，那么只需要计算一次条件，怎么办呢？
我们可以用一个 map 去存它上一次的贡献，如果相同就不管它。
如果不同，那么将两次贡献的差值加入线段树内即可，还要更新为新的贡献值。
提示：如果不想打权值线段树，就使用离散化。
代码
戳我喵~(这是树状数组写法，可以替换成线段树)
const int mod = 1e9 + 7; //不要忘记了modint 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 longconst 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 | 1struct 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;
}