CF1175GYetAnotherPartitonProblem

CF1175G Yet Another Partiton Problem。

非常有启发性和挑战性的题目，超高难度斜率优化。建议先学习 DP 优化 II 斜率优化部分 以及 线段树的高级用法 李超树部分。

2D/1D 动态规划首先考虑决策单调性分治，但是没有决策单调性，因为贡献函数不满足四边形不等式：如当 \(a = \{10, 1, 10\}\) 时，\(w(1, 2) + w(2, 3) = 40\)，而 \(w(1, 3) + w(2, 2) = 31\)。

考虑进行 \(k\) 轮 DP，设上一轮 DP 值为 \(g\)，当前轮为 \(f\)，则每轮 DP 形如

\[f_i = \min_{j = 0} ^ {i - 1} g_j + (i - j) \times \left(\max_{k = j + 1} ^ i a_k\right)

\]

假设 \(i\) 固定，令 \(v_j = \max\limits_{k = j + 1} ^ i a_k\)。显然，\(v_j\) 随着 \(j\) 增大而单调递减。对于 \(v\) 值相同的一段区间 \([l, r]\ (l\leq r ，设对应的 \(v\) 值为 \(d\)，即 \(d = v_l = v_{l + 1} = \cdots = v_r\)。拆开柿子，我们需要最小化 \(g_i - d\times i\)。对于每个 \([l, r]\) 块，维护 下 凸包 \((i, g_i)\)，查询最值点 \(p\) 只需用斜率 \(d\) 切凸包即可。这是 斜率优化 的思想。 这一步相当于 \(v\) 值相同的区间 仅保留唯一决策点。

设对于 \(v\) 值相同的极长区间 \([l_j, r_j]\)，用斜率 \(v_{l_j}\) 切对应凸包得到的最值点为 \(p_j\)。对于所有这样的大区间，我们相当于要求 \(\min g_{p_j} + (i - p_j)\times v_{p_j}\)，记作 \(F(l_j, r_j)\)。其中 \(g, v, p_j\) 都是已知量，只有 \(i\) 未知，所以 \(F(l_j, r_j)\) 是 \(i\) 的 一次函数，即关于 \(i\) 的直线。因此，每个极长区间都描述了一条直线，我们需要求出这些直线在某处取值的最小值，经典李超树。 这一步相当于对于 \(v\) 值不同的区间，用李超树维护每个 区间最优点对应的直线。

还剩最后一个问题：\(i\) 增大时，\(v_j\) 也会随之改变。\(v_j\) 容易用单调栈维护，但合并两个极长区间的信息有些棘手：

• 为保证时间复杂度，必须启发式合并凸包，因此需要使用双端队列维护凸包。


• 注意到 \(i\to i + 1\) 时，\(v\) 值受到影响位置的是 \([1, i]\) 的一端后缀，且受到影响的区间 \([l, i]\) 的 \(v\) 值相同，即 \([l, i]\) 是极长区间。因此，我们不需要删除直线，而是将李超树 可持久化 / 可撤销，那么 \(i + 1\) 时刻的李超树 \(T_{i + 1}\) 可由在 \(l - 1\) 时刻的李超树 \(T_{l - 1}\) 的基础上新增一条直线得到。不难发现 \(l - 1\) 即单调栈栈顶。

综上，我们使用斜率优化，可持久化李超树，启发式合并凸包，单调栈四种算法，在 \(\mathcal{O}(nk\log n)\) 的时间内解决了问题。

#include
using namespace std;
#define ll long long
#define mem(x, v) memset(x, v, sizeof(x))
const int N = 2e4 + 5;
ll n, K, a[N], k[N], b[N], g[N], f[N], stc[N], top;
ll get(int x, int id) {return k[id] * x + b[id];}
// convex hull
deque d[N];
ll cross(int i, int j, int k) {return (j - i) * (g[k] - g[j]) - (g[j] - g[i]) * (k - j);}
void merge(int x, int y) {
if(d[x].size() while(d[x].size()) {
while(d[y].size() >= 2 && cross(d[x].back(), d[y][0], d[y][1]) <= 0) d[y].pop_front();
d[y].push_front(d[x].back()), d[x].pop_back();
}
else {
while(d[y].size()) {
while(d[x].size() >= 2 && cross(d[x][d[x].size() - 2], d[x][d[x].size() - 1], d[y][0]) <= 0) d[x].pop_back();
d[x].push_back(d[y].front()), d[y].pop_front();
} d[y].swap(d[x]);
}
}
ll query(ll k, int id) {
int l = 0, r = d[id].size() - 1;
while(l int m = l + r >> 1, x = d[id][m], y = d[id][m + 1];
if((y - x) * k >= g[y] - g[x]) l = m + 1; else r = m;
} return g[d[id][l]] - k * d[id][l];
}
// persistent lichao segment tree
int node, R[N], ls[N <<5], rs[N <<5], mx[N <<5];
void modify(int pre, int &x, int l, int r, int v) {
mx[x = ++node] = mx[pre], ls[x] = ls[pre], rs[x] = rs[pre];
int m = l + r >> 1;
if(get(m, v) if(get(l, v) else if(get(r, v) }
ll query(int l, int r, int p, int x) {
ll ans = get(p, mx[x]);
if(!x || l == r) return ans;
int m = l + r >> 1;
if(p <= m) return min(ans, query(l, m, p, ls[x]));
return min(ans, query(m + 1, r, p, rs[x]));
}
int main() {
cin >> n >> K, b[0] = 1e18;
for(int i = 1; i <= n; i++) cin >> a[i], g[i] = 1e12;
for(int i = 1; i <= K; i++, top = node = 0) {
mem(ls, 0), mem(rs, 0), mem(mx, 0);
for(int i = 1; i <= n; i++) d[i].clear(), d[i].push_back(i - 1);
for(int i = 1; i <= n; i++) {
while(top && a[stc[top]] <= a[i]) merge(stc[top--], i);
k[i] = a[i], b[i] = query(a[i], i);
modify(R[stc[top]], R[i], 1, n, i);
f[i] = query(1, n, i, R[i]), stc[++top] = i;
} swap(f, g);
} cout < return 0;
}