G题nlogn做法

贪心地想，吃鱼肯定是从小到大吃。

因此可以将鱼的重量排序后（记为 ），如果存在一个最小的 ，满足 ，说明只能吃完前 条鱼。如果没有这样的 ，那么能吃完所有的鱼。

其实就是考察每条鱼减去所有比它轻的鱼的重量是否大于 。

举个例子：

假设 ，现在可以吃的鱼的重量分别是

我们令每个数减去它前面的数的和，得到

于是可以吃前四条鱼，最终 。

把数据离散化，扫描线后就可以把问题拆解成：动态加入和删除一条鱼，然后维护上述的 每个鱼的重量减去所有比它小的鱼的重量之和，接着在线段树上二分查询答案。

因此写个值域线段树支持单点修改即可。

时间复杂度 。

#include <bits/stdc++.h>
typedef long long i64;
#define F(x, y, z) for (int x = (y); x <= (z); ++x)
#define DF(x, y, z) for (int x = (y); x >= (z); --x)
#define pb push_back
#define eb emplace_back
#define vi vector<int>
using namespace std;
int read() {
	char ch = getchar();
	int x = 0, pd = 0;
	while (ch < '0' || ch > '9') pd |= ch == '-', ch = getchar();
	while ('0' <= ch && ch <= '9') x = x * 10 + (ch ^ 48), ch = getchar();
	return pd ? -x : x;
}
const int maxn = 100005;
int n, m;
struct Seg {
	int l, r, x;
	void in() {
		l = read(), r = read(), x = read();
	}
} seg[maxn];
vi ins[maxn << 1], del[maxn << 1];
int rk1[maxn << 1], rk2[maxn], len1, len2;
#define ls (o << 1)
#define rs (o << 1 | 1)
#define lson ls,l,mid
#define rson rs,mid+1,r
i64 sum[maxn << 2], mx[maxn << 2];
void pp(int o) {
	sum[o] = sum[ls] + sum[rs];
	mx[o] = max(mx[ls], mx[rs] - sum[ls]);
}
void upd(int o, int l, int r, int x, int y) {
	if (l == r) {
		if ((sum[o] += rk2[x] * y) > 0)
			mx[o] = rk2[x];
		else mx[o] = 0;
		return;
	}
	int mid = (l + r) >> 1;
	if (x <= mid) upd(lson, x, y);
	else upd(rson, x, y);
	pp(o);
}
i64 qry(int o, int l, int r, i64 dt) {
	if (l == r) return dt + (m >= mx[o] - dt ? sum[o] : 0);
	int mid = (l + r) >> 1;
	if (mx[ls] - dt > m) return qry(lson, dt);
	return qry(rson, dt + sum[ls]);
}
void work() {
	n = read(), m = read();
	len1 = len2 = 0;
	F(i, 1, n) {
		seg[i].in();
		rk1[++len1] = seg[i].l, rk1[++len1] = seg[i].r;
		rk2[++len2] = seg[i].x;
	}
	sort(rk1 + 1, rk1 + len1 + 1), len1 = unique(rk1 + 1, rk1 + len1 + 1) - rk1 - 1;
	sort(rk2 + 1, rk2 + len2 + 1), len2 = unique(rk2 + 1, rk2 + len2 + 1) - rk2 - 1;
	F(i, 1, len1) ins[i].clear(), del[i].clear();
	F(i, 1, n) {
		auto [l, r, x] = (tuple<int,int,int>){lower_bound(rk1 + 1, rk1 + len1 + 1, seg[i].l) - rk1, lower_bound(rk1 + 1, rk1 + len1 + 1, seg[i].r) - rk1, lower_bound(rk2 + 1, rk2 + len2 + 1, seg[i].x) - rk2};
		ins[l].eb(x), del[r].eb(x);
	}
	i64 ans = 0;
	F(i, 1, len1) {
		for (auto x : ins[i]) upd(1, 1, len2, x, 1);
		for (auto x : del[i]) upd(1, 1, len2, x, -1);
		ans = max(ans, qry(1, 1, len2, 0ll));
	}
	printf("%lld\n", ans + m);
}
int main() {
	int T = read();
	while (T--) work();
	return 0;
}