算法1

(贪心+数据结构优化) $O(50000*log(n)$

时间复杂度

参考文献

参考墨染空大佬的题解；
将操作3：从后往前，找到比当前位置靠前的下一个0的位置。
用栈实现，每次r改变将所有小于等于r且未进过栈的数进栈，栈顶元素即为当前位置靠前的下一个0的位置；

C++ 代码

#include<iostream>
#include<stack>
#include<algorithm>
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;
const int N = 5e4+5;
int n;
struct node{
    int l,r,c;
}a[N];
bool cmp(node a,node b){
    return a.r < b.r;
}
int tr[N];
int lowbit(int x){
    return x & -x;
}
void add(int x){
    for(int i = x ; i < N ; i += lowbit(i)) tr[i]++;
}
int query(int x){
    int res = 0;
    for(int i = x ;  i ; i -= lowbit(i)) res += tr[i];
    return res;
}
void solve(){
    cin >> n;
    for(int i = 0 ; i < n ; ++i){
        cin >> a[i].l >> a[i].r >> a[i].c;
    }
    sort(a,a + n,cmp);
    int cur = 1;
    stack<int> s;
    for(int i = 0 ; i < n ; ++i){
        int l = a[i].l,r = a[i].r,cnt = a[i].c;
        cnt -= query(r) - query(l - 1);
        while(cur <= r) s.push(cur++);
        //每次选择当前可选最大的数 
        while(cnt > 0){
            int t = s.top();
            add(t);
            s.pop();
            cnt--;
        }
    }
    cout << query(50000) << endl;
}

signed main(){
    IOS;
    solve();
    return 0;
}