Deforestation (USACO Silver 2024 December)

砍树、种树类的问题，本质上是一个调度（scheduling）问题，这类问题我们考虑是否有贪心（greedy）的解法。

首先我们从左往右看所有的树和区间约束的时候，可以发现，对于一个区间来说，砍掉左边的树比右边的树更优：因为左边的树砍掉后，右边的树就可以少砍一棵，从而帮助右边的还没有处理到的区间约束的满足。

所以这个使得我们有一个直观的贪心解法：从左到右扫描所有的树，同时跟踪哪些区间是“活跃”的（覆盖当前树的坐标）。我们记录每个区间里的当前被砍掉的树的数量，如果所有活跃的区间被砍掉的树的数量都未达上限（即 $e[i] - t[i]$ ，其中 $e[i]$ 是区间中原有树的数量， $t[i]$ 是区间需要保留的树的数量），则当前树可以被砍掉。

这个算法的复杂度是 $O(NK)$ ，因为对每棵树，我们需要扫描所有活跃的区间一次，而活跃区间数量是 $O(K)$ 的。

下面我们考虑怎样优化这个算法到 $O(N \log K)$ 这样的复杂度：

这里的关键是怎样跟踪哪些区间的限制还允许我们砍树，哪些不能。因为随着我们不断砍树，每个活跃区间剩下可砍的树的数量是变化的，所以直接记录这个数值会导致算法成为 $O(NK)$ 的。我们考虑如何将这个限制转化为不随时间变化的数值。可以找到一个办法：我们不是记录剩下可砍的数量，而是记录 $ans + e[i] - t[i]$ ，首次进入某一个区间时， $ans$ 是到目前为止的答案（即一共砍了多少树）， $e[i]$ 是这个区间一共原有的树的数量， $t[i]$ 是这个区间需要保留的树的数量，这个 $ans + e[i] - t[i]$ 就是在这个区间结束前，最多可以砍的树数量的上限。

这样重写限制的好处，就是我们可以用 multiset 来管理所有目前活跃的区间对总砍树数量的限制，multiset 的最小值就是当前总砍树数量的限制，遍历到一个区间的右边界时，就把这个限制从 multiset 中删除。在下面代码中，maxcut 是所有总砍树数量限制，active 是右边界和总砍树数量限制的 pair。注意这两个集合都需要是 multiset，因为既可能有同样的 $maxcut$ ，也可能有多个区间有相同的右边界。

这样我们从左到右扫描一遍，就得到了答案。

ps：这个解思考有一定难度，如果用线段树，可以有一个理解起来可能更容易的解。我们从种树的角度来考虑：每个区间右侧的树应该优先种，这样我们可以按区间来遍历，把所有区间按右边界排序，不断种树使得达到 $t[i]$ 棵。这时有两个问题：

怎样快速取得当前右边界下最右边的树？把所有合法的树，都加到一个大根的priority queue中间就可以了。
怎样快速统计当前区间已经种了多少树？这是个标准的区间和问题，用线段树就可以了（同时前面需要先做坐标的离散化）。线段树是金组知识点，所以这个解只适用于金组同学。

具体实现见这里。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
#define f first
#define s second
 
struct constraint {
    int l, r;
    int t, e;
    bool operator<(const constraint &c) const {
        return l < c.l;
    }
};
 
int t,n,k;
int a[300005];
constraint cs[300005];  // constraints
multiset<int> maxcut;   // all actual max cut constraints
multiset<pi> active;    // active (right_boundary, maxcut), allow duplicates
 
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d %d", &n, &k);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
        }
        for (int i = 0; i < k; i++) {
            scanf("%d %d %d", &cs[i].l, &cs[i].r, &cs[i].t);
        }
        sort(a, a+n);
        sort(cs, cs+k);  // order constraints by left boundary
        for (int i = 0; i < k; i++) {
            cs[i].e = upper_bound(a, a+n, cs[i].r) - lower_bound(a, a+n, cs[i].l);
        }
        int ans = 0;
        int j = 0;
        for (int i = 0; i < n; i++) {
            int x = a[i];
            while (active.size() && x > active.begin()->f) { // leave a constraint
                maxcut.erase(maxcut.find(active.begin()->s));
                active.erase(active.begin());
            }
            while (j < k && x >= cs[j].l) { // enter a constraint
                if (x <= cs[j].r) {
                    int cap = ans+cs[j].e-cs[j].t;
                    maxcut.insert(cap);
                    active.insert({cs[j].r, cap});
                }
                j++;
            }
            if (maxcut.empty() || ans < *maxcut.begin())
                ans++;
        }
        printf("%d\n", ans);
        maxcut.clear();
        active.clear();
    }
    return 0;
}