P14621 [2019 KAIST RUN Fall] Parklife

· · 题解

春节十二响。

首先按照区间之间的包含关系建一棵树。

其实是森林，但你可以手动添加一个权值为 0 的区间 [1, 10^6]，作为超级根，不影响答案。

那么问题转化为，在树上选若干个点，每个点到根的链上最多有 k 个点被选，最大化权值之和。

:::info[怎么建树？] 将区间按照 l_i 升序排序，l_i 相同的按照 r_i 降序排序。从左往右扫描，维护一个栈，若栈顶区间不包含当前区间，就不断弹出栈顶，直到包含，这时的栈顶就是当前区间的父亲。

正确性显然。 :::

从 DP 凸优化的角度，和贪心的角度是本质相同的，这里说一下前者。

考虑设计一个暴力 DP，f_{u, k} 表示在 u 的子树内的答案。

转移讨论是否选择 u，（设 u 的权值是 a_u），

容易发现固定 u 时，f_{u, k} 关于 k 是上凸的，因为这个转移实际上是，先将所有孩子的直接相加，再做一个 f_k \gets \max \{f_{k-1} + a_u, f_k\} 状物。

这个凸性自然也对应了贪心做法，和似乎也可以建出来一个费用流的模型。

那么考虑维护斜率，也就是差分数组 g_k = f_k - f_{k-1}。g_k 关于 k 是单调不增的，并且，在子树最大深度以后的位置，都是 0。

「先将所有孩子直接相加」就是把上凸壳每一个对应位置高度相加，当然也就是斜率（差分数组 g）对应相加。

「再做一个 f_k \gets \max \{f_{k-1} + a_u, f_k\} 状物」，想象一个上凸壳先向上平移 a_u，再向右平移 1，最后和原来的取 \max。设 p 满足 g_p < a_u 且 p 最小。对于 < p 的位置，平移后的高度并没有原来高，不会改变；对于 \ge p 的位置，会把右半边的上凸壳先平移，然后在 p - 1 和 p 之间插入一条斜率为 a_u 的线段连接两部分。

考虑用堆维护 g 数组。由于有效位置不多，第一种操作启发式合并堆即可；第二种操作，直接将 a_u 丢进堆里即可。

注意到这个做法和直接贪是一样的。

时间复杂度是堆启发式合并的 O(n \log^2 n)。

:::info[代码]

#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)
using namespace std;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using arr = array<int, 2>;
using vec = vector<int>;
using pii = pair<int, int>;
const int N = 2.5e5 + 5;
const int K = 1e6;

int n; array<int, 3> s[N];

int st[N], tp; vec e[N];
priority_queue<i64> f[N];
void Dfs(int u) {
  for (int v : e[u]) {
    Dfs(v);
    if (f[u].size() < f[v].size()) swap(f[u], f[v]);
    vector<i64> tmp;
    while (!f[v].empty()) {
      i64 x = f[u].top(), y = f[v].top();
      tmp.push_back(x + y), f[u].pop(), f[v].pop();
    }
    for (i64 x : tmp) f[u].push(x);
  }
  f[u].push(s[u][2]);
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n, s[n + 1] = {1, K, 0};
  F(i, 1, n) cin >> s[i][0] >> s[i][1] >> s[i][2];
  auto cmp = [&](array<int, 3> x, array<int, 3> y)
    { return x[0] == y[0] ? x[1] > y[1] : x[0] < y[0]; } ;
  sort(s + 1, s + n + 2, cmp);
  st[tp = 1] = 1;
  F(i, 2, n + 1) {
    while (tp && s[st[tp]][1] < s[i][1]) --tp;
    e[st[tp]].push_back(i), st[++tp] = i;
  }
  Dfs(1);
  i64 ans = 0;
  F(i, 1, n) {
    if (!f[1].empty()) ans += f[1].top(), f[1].pop();
    cout << ans << " ";
  }
  return 0;
}

:::