W - Intervals

W - Intervals

dp[i] := iまで見ていて、iが1の時の最大値としたい
すると、あるi未満のjで、dp[i] := max(dp[j]) + iが含まれる区間のコスト　という風にしたくなる
max(dp[j])はセグ木を使えば管理できる

しかし、このままではi,j共に含まれる区間が、重複して加算されてしまう
そこで、上のijが含まれる区間の値をiのみに持たせることにする
これは、dp[i] に入れる値を i+1にもまたがっている区間の合計だけ減らしておき
ある区間lrの右端rに来たら、dp[l] ~ dp[r]にa[m]を遅延セグ木で加算すれば実現できる

Submission #4430121 - Educational DP Contest

digraph<> gl(2 * k5);
digraph<> gr(2 * k5);
void solve() {
    cin >> n >> m;
    na3(l, r, a, m);
    sortt(l, r, a);
    rep(i, m) {
        gl.add(l[i], r[i], a[i]);
        gr.add(r[i], l[i], a[i]);
    }
    SegmentLazyAdd seg(vi(k5 * 2), segMaxl);
    int ad = 0;
    chmax(ma, 0);
    rep(i, 1, n + 1) {
        forg(gi, gl[i])ad += c;
        int res = 0;
        res += seg.getv(0, i);
        chmax(ma, res + ad);
        seg.update(i, res);
        forg(gi, gr[i]) {
            ad -= c;
            seg.add(t, f + 1, c);
        }
    }
    cout << ma << endl;
}