更壞的閱讀體驗：我的CSDN

更新日志

2025/8/29 修改了正確性證明，使其更加直觀。

題目傳送門

洛谷P11453

題目大意

有一條數軸，上面有一些樹，坐標為 \(a_1,a_2,\cdots,a_n\) ?，F在給你 \(k\) 個限制，對于第 \(i\) 個限制，要求 \([l_i,r_i]\) 上必須至少有 \(t_i\) 顆樹。

部分分思路

首先排序 \(a\)，然后將限制按左端點排序。顯然對于第 \(i\) 個限制，保留右邊的 \(t_i\) 顆樹是最不劣的 直觀理解無需證明。
那么，我們遍歷這個限制列表，然后從右端點開始添加樹。時間復雜度 \(\text{O(NK)}\)。
偽代碼實現：

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int n, k;
void solve()
{
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(all(a));
	vector<CONSTRAINTS> constraint(k);
	
	vector<bool> planted(n, 0);
	int ans = 0;
	for (auto i: constraint) {
		int cnt = 0;
		for (int j = n; j; --j) {
			if (i.l <= a[j] && a[j] <= i.r && planted[j]) {
				++cnt;
			}
		}
		for (int j = n; j; --j) {
			if (cnt >= i.t) break;
			if (i.l <= a[j] && a[j] <= i.r && !planted[j]) {
				planted[j] = 1;
				++cnt;
				++ans;
			}
		}
	}
	cout << ans << '\n';
}
int main()
{
	// ios::sync_with_stdio(false);
	// cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

部分分優化（優先隊列，滿分）

考慮將樹和約束放在一起考慮。
按 約束的左端點 / 樹的坐標 為第一關鍵字排序，約束=0/樹=1為第二關鍵字排序。
此外，對于一個約束，再多記錄它的右端點和最大伐木數（區間 \([l_i,r_i]\) 內樹數量減去需要保留的數量）。

再維護一個優先隊列 constraint ，記錄對于某個約束 \(i\) ，數軸上 \([1,r_i]\) 里最優可以砍掉的樹木數量，用一個 pair<int, int> 表示即可，比較函數為以 \(r_i\) 為第一關鍵字（從小到大），最大樹木砍伐數量（從小到大）為第二關鍵字進行排序。
同時，維護當前砍掉的樹の數量ans。
每次若枚舉到約束，則貪心地將約束區間內能砍的樹數量全部砍掉并扔到 constraint 里，即 constraint.push({ans + cut_down, r});
若枚舉到位置為 \(x\) 的樹，則首先檢查優先隊列里的約束，其中 \(r<x\) 的，顯然都不對目前及以后的任何樹造成影響，因此可以直接 pop() 掉。在剩下的 constraint 里，若為空，則沒有能對這棵樹造成威脅的約束了，砍掉，++ans。否則若 constraint.top() 的最大伐木數量大于當前的 ans，即 ans < constraint.top().first ，同樣 ++ans。

AC代碼（不要走，后面有采但）

#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
typedef pair<int, int> pii;
const int N = 1e5 + 5;
int n, k;
void solve()
{
	cin >> n >> k;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	sort(all(a));
	// l/coord
	// type: 0 constrant; 1 tree
	// r
	// maximum amount of tree that can be cut down
	vector<pair<pii, pii>> event;
	for (auto i: a) {
		event.push_back({{i, 1}, {0, 0}});
	}
	for (int i = 1; i <= k; ++i) {
		int l, r, t;
		cin >> l >> r >> t;
		event.push_back({{l, 0}, {r, upper_bound(all(a), r) - lower_bound(all(a), l) - t}});
	}
	sort(all(event));

	int ans = 0;

	// // 用優先隊列記錄最有約束性的約束
	// 記錄對于當前枚舉到的樹的約束條件
	priority_queue<pii, vector<pii>, greater<pii>> constraint;
	for (auto i: event) {
		int type = i.first.second;
		if (type == 0) { // a constraint
			int l = i.first.first, r = i.second.first, t = i.second.second;
			// 顯然當我們遇到一個限制時, 當前砍掉的樹數量一定是[1,r]最優的
			constraint.push({ans + t, r});
		}
		else { // a tree
			int pos = i.first.first;
			while (constraint.size()) {
				if (constraint.top().second >= pos) break;
				constraint.pop();
			}
			ans += constraint.empty() || constraint.top().first > ans;
		}
	}
	cout << ans << '\n';
}
int main()
{
	// freopen("deforestation.in", "r", stdin);
	// freopen("deforestation.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}

正確性證明

如此微妙的思路，當然需要一篇詳細的證明，不要像某谷題解，第一篇就有一個小天才大蒟蒻的我發了占總評論數75%的問詢評論。（這只是道綠題啊，然后我看題解看了4h沒看懂，一定是題解我的語文問題awa）
后來去看 USACO 官方題解，
還是

正文：
證：
一些顯然的引理：
引理0：ans表示的是-1e9到截止目前最后一顆處理的樹的坐標內最多砍樹數 （由其只在處理樹時更新的計算方法可得）
引理1：處理一個區間時，ans所表示坐標必然小于目前區間左端點 \(l\) （由初始化時的排序可得）
引理2：處理一顆樹時，所有囊括其的區間必然全部按右端點從左到右在 constraint（下文簡稱 q） 里 （由初始化時的排序可得）

由引理1，顯然

q.emplace({ans + p, r});

這步操作中，ans+p 并不會造成區間i-1 和 區間i 重疊部分的樹的重復計數，因為

• 首先 ans 根本就沒表示一個區間的右端點
• 其次由引理1 ans 沒有重疊

接下來我們討論，為什么 q 按右端點從左到右排序一定是正確的，即為什么這樣排在優先隊列最前面的，右端點最左 的前提下 其截止此區間可砍伐樹木數量最小的 約束是最“緊迫”，需要優先考慮的？
我們稱右端點最左的限制為 \(A\) ，其后的限制為 \(B\)。\(A\) 之所以 “最緊迫”，是因為：

• 其有效范圍（\(≤r_A\)）最早結束，一旦超過 \(r_A\)，無法用后續樹彌補其保留要求，若不優先處理會直接違反限制。
• 優先滿足 \(A\) 能讓更靠右的樹（同時屬于 \(A\) 和 \(B\)）保留下來，為后續限制（如 \(B\)）留出更多砍伐空間，最大化總砍伐數。

使用例子證明緊迫性的約束的必要的

要理解“右端點最左的限制是最緊迫的”，以及違反它的后果，我們可以通過一個具體反例來拆解——先構造場景，再對比“優先滿足緊迫限制”和“違反緊迫限制”兩種選擇的最終結果，從而直觀看到后者的問題。

1. 樹的信息（按坐標從小到大排序）

• 樹A：坐標 x=2
• 樹B：坐標 x=5

2. 限制的信息（按左端點排序，且左端點均≤2，保證能覆蓋樹A）

• 限制1（右端點更左，即“緊迫限制”）：
  區間 [1,3]，最多能砍 p=1 棵樹（意思是：在 [1,3] 里砍樹不能超過1棵）。
• 限制2（右端點更右，非緊迫）：
  區間 [1,6]，最多能砍 p=2 棵樹（意思是：在 [1,6] 里砍樹不能超過2棵）。

3. 事件排序（按“坐標/左端點”升序，限制優先于樹）

根據算法的事件規則：

• 限制的“排序鍵”是左端點（均為1），樹的“排序鍵”是坐標（2和5）；
• 同排序鍵下，限制優先于樹。
  因此事件順序為：
  限制1 → 限制2 → 樹A（x=2） → 樹B（x=5）

“優先滿足緊迫的限制”的正確選擇

算法的優先隊列（小根堆）以“右端點”為第一關鍵字，因此處理樹A時，堆中先彈出右端點更左的限制1（而非限制2），決策過程如下：

1. 處理限制1：堆中加入 (ans + p, r) = (0 + 1, 3)（ans初始為0）。
2. 處理限制2：堆中加入 (0 + 2, 6)，此時堆頂是限制1（右端點3 < 6）。
3. 處理樹 A(x=2)：
   • 檢查堆頂（限制1）：右端點3 ≥ 2，有效。
   • 限制1的 ans+p=1 > 當前 ans=0，說明可砍樹A（砍后 ans=1）。
4. 處理樹 B(x=5)：
   • 先彈出堆頂（限制1的右端點3 < 5，無效），此時堆頂是限制2。
   • 限制2的 ans+p=2 > 當前 ans=1，說明可砍樹B（砍后 ans=2）。

最終結果：砍2棵樹，同時滿足兩個限制（限制1砍1棵，限制2砍2棵）。

“不優先滿足緊迫的限制”的后果

假設我們“不優先處理右端點最左的限制1”，反而先處理限制2，會發生什么？

1. 處理限制1和限制2后，堆中仍有兩個限制，但我們刻意忽略堆頂的限制1，直接用限制2判斷樹A：
   • 限制2的 ans+p=2 > 當前 ans=0，于是砍樹A（ans=1）。
2. 此時，我們違反了限制1：限制1要求 [1,3] 最多砍1棵樹，而樹A在 [1,3] 內，砍樹A本身是允許的（沒超1棵），但問題在后續——如果有第三棵樹C（x=3，也在 [1,3] 內）：
   • 處理樹C時，若仍忽略限制1，用限制2判斷：限制2的 ans+p=2 > 當前 ans=1，會繼續砍樹C（ans=2）。
   • 此時限制1被打破（[1,3] 內砍了2棵樹，超過p=1的上限），導致結果非法。

關鍵：為什么“違反緊迫限制”必然導致問題？

右端點最左的限制（如限制1 [1,3]）有一個核心特點：它的“管轄范圍”最小，且沒有后續擴展的可能。

• 對于右端點更右的限制（如限制2 [1,6]），即使當前沒處理，后續的樹（如x=5、x=6）仍在其范圍內，有“補救”的機會；
• 但對于右端點最左的限制（如限制1 [1,3]），一旦錯過其范圍內的樹（如x=2、x=3），后續再也沒有樹屬于這個區間——如果此時超了限制的砍樹數量，沒有任何辦法修正（因為無法“撤銷”已砍的樹），直接導致結果非法。

反證法：若不優先處理緊迫限制，必存在非法情況

假設存在一種最優方案，沒有優先處理右端點最左的限制R（即處理R范圍內的樹時，先用了其他右端點更右的限制R'）。

• 由于R的右端點 < R'的右端點，R的管轄范圍是R'的子集（如R [1,3] 是R' [1,6] 的子集）。
• 若在R的范圍內砍樹數量超過了R的p值（因為沒優先用R的限制控制），則無論后續如何處理R'，R的限制都已被打破——該方案非法。
• 若在R的范圍內砍樹數量未超R的p值，那么“優先用R”和“先用R'”的結果一致（砍樹數量相同），但“優先用R”能更早排除無效限制（避免后續誤判），不會比“先用R'”差。

因此，“不優先處理緊迫限制”要么導致非法，要么不優于“優先處理”，即優先處理右端點最左的限制是唯一正確的選擇。

總結

違反右端點最左的限制，本質是“用范圍更大的限制替代范圍更小的限制”，會導致：

1. 小范圍限制的砍樹數量失控（因為沒有及時用其p值約束）；
2. 最終結果可能違反小范圍限制的規則，變得非法；
3. 即使暫時沒失控，也無法獲得比“優先處理緊迫限制”更優的結果。

這就是為什么右端點最左的限制是“最緊迫”的，必須優先處理。