CF1787H Codeforces Scoreboard
校内测试的一道题， 考试时根本没动。。
题面
考虑 \(k\) 比较大的放前面肯定优， 然后修门挨着放也肯定优， 所以先按 \(k\) 排个序， 然后我们就只考虑每个门修不修。
设计状态 \(f[i][j]\) 表示前 \(i\) 个点， 有 \(j\) 个门取 \(b - kt\)， 少送回去的最少人数。
设 \(c[i]\) 表示 \(b[i] - a[i]\)。
\[f[i][j] = \left\{ \begin{matrix} f[i - 1][j] + c[i] \quad j = 0 \\ min \{f[i - 1][j] + c[i], f[i - 1][j - 1] + k[i] \times j\} \quad j > 0 $ \end{matrix} \right. \]时间复杂度 \(O(n ^ 2)\)， 这里不考虑 \(k[i] \times j > c[i]\)， 虽然有点不严谨， 但是不影响答案， 因为它肯定比直接取 \(c[i]\) 更劣， 而且还方便后面的优化。
这里先人类智慧的感受一下， \(j\) 大了， 那么后面的损失就会'越来越大'(此处不严谨)， 太少了， 也不行， 所以要在中间某个位置， 取最合适， 似乎可以感受到这个 \(f[i]\) 是下凸的， 再打表看一看， 发现确实是， 所以考虑一下怎么优化。
因为要一个一个取min， 所以我们预估的优化就是， 可以通过神奇方法， 批量处理， 也就是在某个区间我们清楚的知道谁大谁小。 那么就考虑这个函数有什么性质， 下凸的， 也就是差分数组单增。
所以就有
\(f[i][j] = c[i] + \sum_{k = 1}^jg[i][k]\)
$g[i][j] = g[i−1][j−1] + min ( g[i−1][j] + c[i], k[i] \times j) − min(g[i−1][j−1] + c[i], k[i] \times (j−1)) $
再仔细观察， \(k[i] \times j\) 与 \(k[i] \times (j - 1)\) 差了 \(k[i]\)， 可以猜测加归纳加分讨， g[i - 1][j] 的增速大于 \(k[i]\) 的增速， 也就是这两个函数只有至多一个交点， 找到这个交点就可以直接得到他们的大小关系。
所以我们维护 \(g\) 数组， 用平衡树维护， 插入一个点， 后缀加。 找这个交点可以二分， 但考虑如果我们使用 FHQtreap， 那么他自带分治结构， split的时候就可以直接二分找到交点了， 所以用 FHQtreap 维护即可做到 \(O(nlogn)\) 时间复杂度。
最后答案就是 \(\sum b[i] - min(f[n][j])\)， 也就是 \(g\) 数组的最小前缀和， 直接取所有的负数即可， 因为 \(g\) 数组单增。
代码
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define int long long
struct FHQ{
int ch[N][2], val[N], key[N], siz[N], add[N], rt, tot;
#define ls(u) ch[u][0]
#define rs(u) ch[u][1]
void clear() {
for (int i = 1; i <= tot; i++)
ls(i) = rs(i) = val[i] = key[i] = siz[i] = add[i] = rt = 0;
tot = 0;
}
void NewNode(int v) { ++tot; val[tot] = v; siz[tot] = 1; key[tot] = rand(); }
void pushdown(int u) {
if (add[u]) {
if (ls(u)) val[ls(u)] += add[u], add[ls(u)] += add[u];
if (rs(u)) val[rs(u)] += add[u], add[rs(u)] += add[u];
add[u] = 0;
}
}
void pushup(int u) { siz[u] = siz[ls(u)] + siz[rs(u)] + 1; }
void split(int u, int &L, int &R, int lft, int k, int c) {
if (!u) return L = R = 0, void();
pushdown(u);
if (val[u] + c > (lft + siz[ls(u)] + 1) * k)
split(ls(u), L, ls(R = u), lft, k, c);
else split(rs(u), rs(L = u), R, lft + siz[ls(u)] + 1, k, c);
pushup(u);
}
int merge(int L, int R) {
if (!L || !R) return L + R;
pushdown(L); pushdown(R);
if (key[L] > key[R])
return rs(L) = merge(rs(L), R), pushup(L), L;
else
return ls(R) = merge(L, ls(R)), pushup(R), R;
}
int qry(int u) {
if (!u) return 0;
pushdown(u);
return (val[u] < 0 ? val[u] : 0) + qry(ls(u)) + qry(rs(u));
}
}T;
int t, n, sum;
struct dr{
int k, a, b, c;
bool operator < (const dr &x) const {
return k > x.k;
}
}a[N];
signed main() {
// freopen("faded.in", "r", stdin);
// freopen("faded.out", "w", stdout);
srand(time(NULL));
scanf("%lld", &t);
while (t--) {
scanf("%lld", &n);
sum = 0; T.clear();
for (int i = 1; i <= n; i++)
scanf("%lld%lld%lld", &a[i].k, &a[i].b, &a[i].a),
sum += a[i].b, a[i].c = a[i].b - a[i].a;
sort(a + 1, a + 1 + n);
for (int i = 1; i <= n; i++) {
int L, R;
sum -= a[i].c;
T.split(T.rt, L, R, 0, a[i].k, a[i].c);
T.NewNode((T.siz[L] + 1) * a[i].k - a[i].c);
T.val[R] += a[i].k, T.add[R] += a[i].k;
T.rt = T.merge(L, T.merge(T.tot, R));
}
printf("%lld\n", sum - T.qry(T.rt));
}
return 0;
}