思路:

因为值域比较小，我们可以用权值树状数组维护区间和来知道在当前区间中，已经填了多少个数了。如果你已经看过朴素版贪心（暴力枚举区间，找最靠近右端点的一个未被填的位置）求解后，发现这样有可能会超时的，主要就慢在他找位置填这一步。所以这里我用双端链表将所有可填的位置连起来，这样就可以实现O(1)了。具体就是把区间按右端点位置存起来，然后遍历1~N，每遍历一个位置就将这个位置插入链表的最后一个位置，最后遍历以这个为右端点的区间，根据要求从链表尾部依次填一定满足区间范围且最优。

时间复杂度 O(N)

代码

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

typedef long long ll;
typedef pair<int, int> pii;
const int N = 5e4 + 10;

int ne[N], pre[N], tail; // tail 尾节点
int tr[N], ans;
vector<pii> q[N];

int lowbit(int x)
{
    return x & -x;
}

void add(int x)
{
    for(int i = x; i < N; i += lowbit(i)) tr[i] += 1;
}

int query(int x)
{
    int res = 0;
    for(int i = x; i > 0; i -= lowbit(i)) res += tr[i];
    return res;
}

void link(int i)
{
    ne[i] = tail;
    pre[i] = pre[tail];
    ne[pre[tail]] = i;
    pre[tail] = i;
}

int main()
{
    int n; cin >> n;
    for(int i = 1; i <= n; i ++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        //按右端点存储区间询问
        q[b + 1].push_back({a + 1, c});
    }
    tail = 0;
    ne[tail] = pre[tail] = -1;
    for(int i = 1; i < N; i ++)
    {
        link(i); // 将 i 插入链表最后一个位置
        for(auto t : q[i])
        {
            int a = t.first, c = t.second;
            //查询区间的需求
            int need = c - (query(i) - query(a - 1));
            while(need > 0) {
                need --; ans ++;
                int x = pre[tail];
                add(x);
                //删除该节点
                ne[pre[x]] = tail;
                pre[tail] = pre[x];
            }
        }
    }
    cout << ans << "\n";
    return 0;
}