はまやんはまやんはまやん

hamayanhamayan's blog

Noelちゃんと電車旅行 [yukicoder No.631]

https://yukicoder.me/problems/no/631

解法

https://yukicoder.me/submissions/228091

遅延評価セグメントツリーを作って計算していこう。
以降0-indexedで説明する。
i番目にT[i] - 3 * (N - i - 1)を格納しておき、[0,N)の最大値を取ってくれば答えになる。
[L,R]の区間のT[i]に+Dをするが、これは遅延評価セグメントツリーを使って解決しよう。
なので、区間add区間maxの遅延評価セグメントツリーが構築できれば答えることができる。

(この構築が難しいのだがこのサイトを参考に作ろう)
遅延評価セグメントツリーの練習問題としては最適。

typedef long long ll;
int N; ll T[101010]; int M;
LazySegTree<ll, 1 << 18> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N - 1) cin >> T[i];
    rep(i, 0, N - 1) st.update(i, T[i] + 3 * (N - i - 1));
    cin >> M;

    rep(i, 0, M) {
        int L, R, D; cin >> L >> R >> D;
        L--; R--;
        st.lazyupdate(L, R + 1, D);
        ll ans = st.get(0, N);
        printf("%lld\n", ans);
    }
}