CF1175G Yet Another Partiton Problem 是什么问题？
摘要：$text{Solution}$ 有关斜率优化的强势套娃题，感觉套出了巅峰 ~~我整整写了 5 个小时、、、~~ 简单 $dp$ $$ f_{i,j} = f_{i-1,k-1} + (j-k+1)m
\(\text{Solution}\)
有关斜率优化的强势套娃题，感觉套出了巅峰
我整整写了 5 个小时、、、
简单 \(dp\)
\[f_{i,j} = f_{i-1,k-1} + (j-k+1)\max_{l=k}^j a_l
\]
固定这个最大值，于是原序列可用笛卡尔树结构表示
考虑左侧对 \(mid\) 的贡献，显然斜率优化维护一个下凸壳即可，找到最小的 \(b=f_k-k a_{mid}\)
左侧对右侧的贡献，此时 \(\max=a_{mid}\)，这个最大值对右侧均有贡献 \(b+a_{mid} \times (j+1)\)
不能把右侧都遍历一边，因为笛卡尔树区间长度和没保证，但注意到贡献是个 \(kx+b\) 的形式，于是可以李超线段树维护。
回溯要合并两个凸包，为保证复杂度，要启发式合并，支持两端插点，用 deque 即可
没了。。。
写的时候不想建笛卡尔树这样优美的分治结构，偷懒只用单调栈扫一遍
于是又要写可持久化李超线段树，不小心写错，然后就糟糕了
更糟糕的是 \(dp\) 写了个 \(f_{i,j}=f_{i-1,k}+(j-k)\max_{l=k+1}^j a_l\)
然后单调栈中的点维护的凸包区间就要是包括前一个点而不包括自己，细节特多（主要是一开始没想清楚），且非常不优美，虽然是微妙的差距，但没想清楚就痛苦了 \(5\) 个小时
\(\text{Code}\)
#include <bits/stdc++.h>
using namespace std;
template<typename Tp>
void read(Tp &x) {
x = 0; char ch = getchar(); int f = 0;
for(; !isdigit(ch); f |= (ch == '-'), ch = getchar());
for(; isdigit(ch); x = (x<<3)+(x<<1)+(ch^48), ch = getchar());
}
const int N = 20005, inf = 4e8;
int n, K, a[N], f[2][N], stk[N], rt[N];
struct line{int k, b;};
struct SegmentTree {
line tr[N * 17]; int size, fl[N * 17], ls[N * 17], rs[N * 17];
int calc(line a, int x){return a.k * x + a.b;}
double ISC(line a, line b){return 1.0 * (b.b - a.b) / (a.k - b.k);}
void insert(int &p, int o, int l, int r, line k) {
p = ++size, tr[p] = tr[o], fl[p] = fl[o], ls[p] = ls[o], rs[p] = rs[o];
if (!fl[p]) return tr[p] = k, fl[p] = 1, void();
int f1 = calc(tr[p], l), f2 = calc(tr[p], r), f3 = calc(k, l), f4 = calc(k, r);
if (f1 <= f3 && f2 <= f4) return;
if (f3 <= f1 && f4 <= f2) return tr[p] = k, void();
if (l == r) return;
int mid = l + r >> 1; double z = ISC(tr[p], k);
if (f1 >= f3) {
if (z <= mid) insert(ls[p], ls[o], l, mid, k);
else insert(rs[p], rs[o], mid + 1, r, tr[p]), tr[p] = k;
}
else {
if (z > mid) insert(rs[p], rs[o], mid + 1, r, k);
else insert(ls[p], ls[o], l, mid, tr[p]), tr[p] = k;
}
}
int query(int p, int l, int r, int x) {
if (!p || !fl[p]) return inf;
int res = calc(tr[p], x), mid = l + r >> 1;
if (l == r) return res;
if (x <= mid) return min(res, query(ls[p], l, mid, x));
return min(res, query(rs[p], mid + 1, r, x));
}
}seg;
struct point{int x, y;};
#define deq deque<point>
struct ConvexHull {
deq d[N];
double slope(point a, point b){return 1.0 * (b.y - a.y) / (b.x - a.x);}
void merge(deq &a, deq &b) {
if (!a.size()) return; if (!b.size()) return swap(a, b), void();
if (a.size() < b.size()) {
for(int i = a.size() - 1; ~i; i--) {
while (b.size() > 1 && slope(b[0], b[1]) <= slope(a[i], b[0]))
b.pop_front();
b.push_front(a[i]);
}
}
else {
for(auto k : b) {
while (a.size() > 1 && slope(k, a.back()) <= slope(a.back(), a[a.size() - 2]))
a.pop_back();
a.push_back(k);
}
swap(a, b);
}
}
int query(deq &a, int k) {
if (!a.size()) return inf;
while (a.size() > 1 && slope(a[0], a[1]) <= k) a.pop_front();
return a[0].y - k * a[0].x;
}
}cv;
int main() {
read(n), read(K);
for(int i = 1, j = 0; i <= n; i++) read(a[i]), j = max(j, a[i]), f[1][i] = i * j;
for(int i = 2; i <= K; i++) {
int top = 0; seg.size = 0;
for(int j = 1, b; j <= n; j++) {
cv.d[j].clear();
if (top) {
cv.d[j].push_back(point{stk[top], f[i & 1 ^ 1][stk[top]]});
for(; top && a[j] >= a[stk[top]]; --top) cv.merge(cv.d[stk[top]], cv.d[j]);
}
b = cv.query(cv.d[j], a[j]), rt[j] = rt[stk[top]];
if (b != inf) seg.insert(rt[j], rt[stk[top]], 1, n, line{a[j], b});
f[i & 1][j] = seg.query(rt[j], 1, n, j), stk[++top] = j;
}
}
printf("%d\n", f[K & 1][n]);
}