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); } }