CS Academy Popcorn

发表于 | 分类于

Description

你有\(n\)包生爆米花，其中第\(i\)包美味度为\(C_i\)，要求加热用时在\([A_i, B_i)\)中。

你还有\(m\)个烤箱。你可以把多包爆米花放在同一个烤箱里，但是要求同一个烤箱的加热时间要是一致的，即放在同一个烤箱里的爆米花的加热时间区间交集非空。当然，你也可以放弃一些爆米花。求最后烤出来的爆米花的美味度之和的最大值。

\(1\leq m\leq n\leq 200000, 1\leq A_i\leq B_i\leq 200000, \sum_{i = 1}^n C_i\leq 10^9\)。

Solution

aji卡常野蛮，，，

考虑补集转换……假设所有爆米花都可以烤好，然后我们再去掉烤不好的。

假设我们知道了\(m\)个烤箱的时间安排……如果说有一个爆米花加热时间区间和任意一个时间安排都不相交的话，那么这个爆米花就是烤不好的。问题就转化成了合理的安排烤箱时间，来最小化烤不好的爆米花的美味度和。

既然有个数限制，那么就考虑wqs二分吧！那么假设当前二分代价为\(s\)，那么我们很显然可以用一个\(O(n^2)\)的DP来处理，并且注意到这个DP只用到了前缀最小值和区间加单点改，所以很显然可以用线段树来优化。

但很不幸的事情事线段树会被卡常致死（写了二进制分组照样也被卡常了，只是没线段树这么惨烈而已），这就意味着我们要用一个复杂度更低/常数更小的数据结构来完成这个任务。

看了一下大爷们的代码发现这个东西可以并查集……我们考虑将DP状态\(d_i\)差分一下得到\(\nabla d_i\)，那么如果说\(\sum_{i = l}^r \nabla d_i < 0\)的话，那么\(d_r < d_{l - 1}\)。因此我们将序列差分之后，我们可以规定每个点向右边第一个比它小的地方认父（不存在的话就当根），那么每个点的根就是从它往右走的最大值。至于修改之后重新处理这个关系的话，我们注意到一段前缀的最小值只可能不断右移，如果说\(d_l < d_r(l < r)\)的话那么这个关系以后会一直存在，因此我们记录每个点往左比它大的地方最远是哪里（从那个地方到这里视为一块，这里的最小值一定是该点或者再往右），这样重新处理关系的话只需要不停的往前扫每一个块就行了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <functional>
#include <utility>
#include <vector>
using ll = long long;
const int maxn = 200005;
const int maxno = maxn << 2;

using pii = std::pair<ll, ll>;
pii val[maxn];
int p[maxn], left[maxn];
int get_fa(int x) {
  if(x == p[x]) return x;
  else return (p[x] = get_fa(p[x]));
}
void upd(int x) {
  while(val[x].first < 0LL && left[x] > 0) {
    int u = get_fa(left[x] - 1);
    p[u] = x; val[x].first += val[u].first;
    left[x] = left[u];
  }
}

using seg = std::pair<int, ll>;
int n, bi; std::vector<seg> V[maxn];
pii dp(ll cost) {
  ll sumv = 0;
  // build_tree(1, 1, bi);
  for(int i = 0; i <= bi + 1; i ++) {
    val[i] = pii(0, 0);
    p[i] = left[i] = i;
  }
  for(int i = 1; i <= bi; i ++) {
    for(auto &p : V[i]) {
      int l = p.first; ll v = p.second;
      sumv += v;
      if(true) {
        val[get_fa(0)].first += v;
        val[get_fa(l)].first -= v;
        upd(get_fa(l));
      }
    }
    pii tmp = val[get_fa(0)];
#ifdef LOCAL
    printf("tmp[%d] : (%lld, %lld)\n", i, tmp.first, tmp.second);
#endif
    tmp.first += cost; tmp.second += 1LL;
    pii f = tmp;
    val[i].first += f.first; val[i + 1].first -= f.first;
    val[i].second = f.second;
    upd(i);
  }
  return std::min(val[get_fa(0)], pii(sumv, 0LL));
}

int main() {
  int m; scanf("%d%d", &n, &m);
  ll L = 0, R = 0, sumv = 0;
  for(int i = 1; i <= n; i ++) {
    int l, r, c; scanf("%d%d%d", &l, &r, &c);
    if(l < r) {
      R += c; sumv += c;
      V[r].push_back(seg(l, c));
      bi = std::max(bi, r);
    }
  }
  pii tmp = dp(0);
#ifdef LOCAL
    printf("tmp : (%lld, %lld)\n", tmp.first, tmp.second);
#endif
  if(tmp.second <= m) {
    printf("%lld\n", sumv - tmp.first);
    return 0;
  }
  while(L < R) {
#ifdef LOCAL
    printf("State (%lld, %lld)\n", L, R);
#endif
    ll M = (L + R) / 2LL;
    pii t = dp(M);
    fprintf(stderr, "t(%lld) : (%lld, %lld)\n", M, t.first, t.second);
    if(t.second <= (ll)m) {
      R = M;
    } else {
      L = M + 1LL;
    }
  }
  pii t = dp(L);
  ll delta = t.first - L * (ll)m;
  printf("%lld\n", sumv - delta);
  return 0;
}