大鱼吃小鱼
题目描述
现在小 w 正在玩一款经典游戏——大鱼吃小鱼。
游戏规则如下：玩家操控一条初始重量为 $x$ 的鱼，它的目标是吃掉所有不超过自身当前重量的鱼。每当吃掉一条重量为 $y$ 的鱼，那么自身重量也会立即增长 $y$。
在游戏过程中，共会陆续出现 $n$ 条鱼。其中第 $i$ 条鱼重 $y_i$，其出现时间段为 $[l_i, r_i)$，即这条鱼会在时刻 $l_i$ 出现，并在时刻 $r_i$ 前消失（包含 $l_i$ 但不包含 $r_i$）。只有当前时刻位于 $[l_i, r_i)$ 时，小 w 才能操作自己的鱼去吃掉它。
鉴于小 w 的手速非凡，吃鱼的耗时可以忽略不计。不过最近他懒癌犯了，因此他打算只选择某一时刻进行捕食，并最大化他的鱼的重量。请计算他的鱼可能达到的最大重量。
输入描述:
第一行给出一个整数 $T(1 \leq T \leq 5 \times 10^4)$，表示数据组数。
对于每组测试数据：
第一行给出两个整数 $n, x (1 \leq n \leq 10^5, \sum{n} \leq 10^5, 1 \leq x \leq 10^9)$，表示鱼的总数与小 w 鱼的初始重量。
后面 $n$ 行，每行为三个整数 $l_i, r_i, y_i (1 \leq l_i < r_i \leq 10^9, 1 \leq y_i \leq 10^9)$。
输出描述:
一个整数，为小 w 的鱼可能达到的最大重量。
示例1
输入
2
2 17
3 4 9
9 11 8
4 1
1 2 2
2 4 1
3 5 2
4 5 3输出
26
4说明
第一组样例中，小 w 鱼的初始重量为 $17$，第一条鱼出现时间段为 $[3,4)$，重量 $9$；第二条鱼出现时间段为 $[9,11)$，重量 $8$ 。显然选择 $[3,4)$ 内的任意时刻进行捕食最优。
第二组样例中，小 w 鱼的初始重量为 $1$，四条鱼的出现时间段与重量依次为：时间段 $[1,2)$，重量 $2$；时间段 $[2,4)$，重量 $1$；时间段 $[3,5)$，重量 $2$；时间段 $[4,5)$，重量 $3$。显然选择 $[3,4)$ 内的任意时刻进行捕食最优。
示例2
输入
1
10 20
13 14 41
10 29 3
3 12 25
10 22 69
12 22 11
14 24 34
18 35 6
5 15 59
8 9 21
18 22 41输出
196
解题思路
对于每个区间 $(l_i, r_i, w_i)$，拆分成三元组 $(l_i, w_i, 1)$ 和 $(r_i, w_i, -1)$。对 $2n$ 个三元组按第一个元素从小到大排序，然后依次遍历用扫描线的思路对每个时刻进行处理。
用一个集合 std::multiset 维护每个时刻有哪些鱼（权值），记当前时刻的三元组为 $(p_0, p_1, p_2)$，如果 $p_2 = 1$ 则把 $p_1$ 插入到集合中，否则 $p_2 = -1$ 则把 $p_1$ 从集合中删去。因此接下来要思考的问题是，初始的权值为 $m$，以题目的规则最终能获得多大的权值？
暴力的做法是从小到大去累加集合中的元素，直到当前权值小于集合中最小的元素停止，时间复杂度为 $O(n^2)$。比起一个一个地去累加，不妨先在集合中二分找到比当前权值大的最小元素，记作 $x$，然后一次性把集合中小于 $x$ 的元素累加到当前权值，该过程最多执行 $O(\log{A})$ 次，$A = \max\{a_i\}$。
如果累加了小于 $x$ 的元素后当前权值大于等于 $x$，那么下一次就会把 $x$ 累加进来，相当于让当前权值翻倍。因为所有元素最大为 $A$，因此在 $O(\log{A})$ 次操作后所有元素都会被累加。
为了快速累加小于 $x$ 的元素，我们可以开一个权值树状数组维护集合中的元素，当然需要进行离散化。
AC 代码如下，时间复杂度为 $O(n \log{n} \log{A})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
array<int, 3> p[N * 2];
int xs[N], sz;
LL tr[N];
int lowbit(int x) {
return x & -x;
}
void add(int x, int c) {
for (int i = x; i <= sz; i += lowbit(i)) {
tr[i] += c;
}
}
LL query(int x) {
LL ret = 0;
for (int i = x; i; i -= lowbit(i)) {
ret += tr[i];
}
return ret;
}
int find(int x) {
int l = 1, r = sz;
while (l < r) {
int mid = l + r >> 1;
if (xs[mid] >= x) r = mid;
else l = mid + 1;
}
return l;
}
void solve() {
int n, m;
cin >> n >> m;
sz = 0;
for (int i = 0; i < n; i++) {
int l, r, x;
cin >> l >> r >> x;
p[i << 1] = {l, x, 1};
p[i << 1 | 1] = {r, x, -1};
xs[++sz] = x;
}
sort(p, p + 2 * n);
sort(xs + 1, xs + sz + 1);
sz = unique(xs + 1, xs + sz + 1) - xs - 1;
LL ret = m;
memset(tr, 0, sz + 1 << 3);
multiset<LL> st({0x3f3f3f3f3f3f3f3f});
for (int i = 0; i < n << 1; i++) {
int j = i;
while (j < n << 1 && p[j][0] == p[i][0]) {
if (p[j][2] == 1) st.insert(p[j][1]);
else st.erase(st.find(p[j][1]));
add(find(p[j][1]), p[j][1] * p[j][2]);
j++;
}
if (*st.begin() <= m) {
LL s = m;
while (true) {
auto it = st.upper_bound(s);
s = m + query(find(*prev(it)));
if (s < *it) break;
}
ret = max(ret, s);
}
i = j - 1;
}
cout << ret << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
参考资料
【比赛题目讲解】牛客小白月赛99：https://www.bilibili.com/video/BV182WUeuEuh/
标签：10,int,重量,大鱼吃小鱼,累加,leq,权值 From： https://www.cnblogs.com/onlyblues/p/18377940