Intervals [Educational DP Contest / DP まとめコンテスト W]

https://atcoder.jp/contests/dp/tasks/dp_w

前提知識

• データ構造によるDP更新最適化
• 区間add, 区間max遅延評価セグメントツリー

解説

https://atcoder.jp/contests/dp/submissions/3963076

dp[r] := r文字目まで確定していてr文字目が1であり、それ以降は0である文字列のスコアの最大値
区間系のDPでは、右端の小さい方から順番に処理していく操作をよく行う。
今回もその方法でいく。
R[r] := 右端がrである区間の{l,a}の配列
　
dpを順番に埋めていく。
まず、dp[r]に1を入れる場合は、dp[0]～dp[r-1]の中の最大値を採用する。
次に右端がrである区間を処理していくが、ある区間[l,r]について考えると、影響を受けるのがdp[l], dp[l+1], ..., dp[r]であり、それぞれの要素には+aされる。

↓怪しいけど、残しておく
dp[r]の更新の時点で右端がrである区間を処理するのは、dp[0]～dp[r]がそれより前のdpによって更新されることがなくなったからである。
もし、それぞれの要素で+aをしたあとに、それより前のdpによって更新されると+aが複数回処理される恐れがある

区間最大値と区間addを達成するには遅延評価セグメントツリーを使えばできる。
よって、dpを区間最大値と区間add対応の遅延評価セグメントツリーにすることで解ける。

int N, M;
LazySegTree<ll, 1 << 18> dp;
vector<pair<int, int>> R[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) {
        int l, r, a; cin >> l >> r >> a;
        l--; r--;
        R[r].push_back({ l,a });
    }
 
    rep(r, 0, N) {
        ll opt = dp.get(0, r);
        dp.update(r, r + 1, opt);
        fore(p, R[r]) {
            int l, a; tie(l, a) = p;
            dp.update(l, r + 1, a);
        }
    }
 
    ll ans = dp.get(0, N);
    cout << ans << endl;
}