自动搬运

查看原文

来自洛谷，原作者为

	masonxiong Determination.

搬运于2025-08-24 23:07:27，当前版本为作者最后更新于2024-12-23 21:47:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目分析

这道题似乎就是 CSP-S T2 的加强版

根据 CSP-S T2 得出的经验，我们可以贪心地从左往右删，因为如果在这个位置删满足条件，那么在右边删可能会浪费条件导致不优，但一定不会因为改到右边而多删。

那么这样我们就可以非常简单的写出一个 $O(nk)$ 的暴力贪心了。接下来我们只需要考虑如何将这个算法优化即可。

这里阐述官方题解的优化方法，即用优先队列进行优化，具体实现比较巧妙。

我们将限制按左端点从小到大排序，树按坐标从小到大排序，并将这两个排序后的结果合并起来记为 events。

然后我们开一个优先队列 Q，它的第一位是最多能砍多少棵树，第二位是目前处理到的右端点坐标。它以第二位为第一关键字，第一位为第二关键字的小根堆。

我们扫一遍 events：

若这是一个限制，则我们按照贪心策略尝试将这个限制中所有能砍的树全砍了，即 Q.emplace(answer + p, r);。

若这是一棵树，我们先把所有没有管辖这棵树的限制全都从 Q 中弹出，由于我们已经将 events 排序，所有左端点一定合法，我们只需要判断右端点是否合法即可。

若 Q 中无元素，说明无限制管辖这棵树，自然可以砍掉它，令答案自增；或者若“目前最多砍的树的数量比目前答案要大（Q.top().first > answer）”，说明这个限制中的树我们还没有砍完，那我们也可以砍掉这棵树。

代码

#include <bits/stdc++.h>
using namespace std;

const int Maxn = 5e5 + 5;
int t, n, k, l, r, p;
int trees[Maxn];

int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	for (cin >> t; t--; ) {
		cin >> n >> k;
		for (int i = 0; i < n; i++)
			cin >> trees[i];
		sort(trees, trees + n);
		vector<tuple<int, int, int, int>> events;
		// 第一位是（限制：左端点 / 树：坐标），第二位表示类型（0：限制 / 1：树）。
		// 第三位是（限制：右端点 / 树：无意义），第四位是（限制：这个区间内还能砍多少棵树 / 树：无意义）。
		// 特别注意第二位的类型不能调换顺序，因为我们要先处理限制再处理树。
		for (int i = 0; i < n; i++)
			events.emplace_back(trees[i], 1, 0, 0);
		while (k--) {
			cin >> l >> r >> p;
			events.emplace_back(l, 0, r, upper_bound(trees, trees + n, r) - lower_bound(trees, trees + n, l) - p /* 计算区间内还能砍多少棵树。 */);
		}
		sort(events.begin(), events.end());
		// 将所有东西按照左端点从小到大排序。
		priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
		// 第一位是最多能砍多少棵树，第二位是目前处理到的右端点坐标。
		// 以第二位为第一关键字，第一位为第二关键字的小根堆。
		int answer = 0;
		for (const auto& event : events) {
			tie(l, k, r, p) = event;
			if (k == 0) {
				Q.emplace(answer + p, r);
				// 将这个限制所对应的区间内的树全都砍掉，并更新右端点。
			} else {
				for (; !Q.empty() && Q.top().second < l; Q.pop());
				// 将未包含这棵树的限制全都清除掉。
				answer += Q.empty() // 没有限制可以管辖这棵树，当然可以砍掉。
						  || Q.top().first > answer; // 这个限制还没有砍完，根据贪心策略我们能砍就砍。
			}
		}
		cout << answer << '\n';
	}
	return 0;
}