题解

感觉我在 ABC/CF 做过 100 道这种题。

定义 $dp[i][j]$ 为前 $i$ 个位置最后一个 $1$ 在 $j$ 时的最大值。转移很简单，按右端点排序然后双指针。

然后简单线段树优化 DP 即可。

namespace cjdst{
    /*
    class Segtree
    经过改造后实现：modify 单点加，query 区间最大值。
    */
    
    void solve(){
		int n, m;
		std::cin >> m >> n;
		std::vector <node> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i].l >> a[i].r >> a[i].v;
		}
		std::sort(a.begin() + 1, a.begin() + n + 1);
		Segtree <ll> dp(m);
		dp.modify(0, 0, 0x3f3f3f3f3f3f3fll);
		int l = 1;
		for(int i = 1; i <= m; i++){
			std::map <int, ll> mp;
			while(l <= n && a[l].r == i){
				mp[a[l].l] += a[l].v;
				l++;
			}
			if(mp.empty()){
				dp.modify(i, i, 0x3f3f3f3f3f3f3fll + dp.query(0, i - 1));
				continue;
			}
			dp.modify(i, i, 0x3f3f3f3f3f3f3fll + dp.query(0, i - 1));
			for(auto it:mp){
				dp.modify(it.first, i, it.second);
			}
		}
		std::cout << dp.query(0, m) << '\n';
	}
}

时间复杂度：$O(n\log n+m\log m)$。