AALC001 B - Lazy Segment Tree
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- B - Lazy Segment Tree
- 難易度
- -
長さ の非負整数列 に対して、次の 2 種類のクエリを合計 個処理する問題です()。
1 l r x: のそれぞれに を足す。2 l r: を出力する。
区間への加算と区間の最小値の取得なので、遅延評価セグメント木を使います。区間 の全要素に を足すと、その区間の最小値もちょうど 増えます。そのため、各ノードには「担当区間の最小値」だけを持たせ、作用は「 を足す」、作用の合成は「足す値の和」とすればよいです。
どちらの操作も なので、全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/lazy-segtree.hpp"
void solve() { LL(N, Q); VL(A, N); RAddMinQ<ll> seg(A); rep(Q) { LL(q); if (q == 1) { LL(l, r, x); seg.apply(l - 1, r, x); } else { LL(l, r); print(seg.prod(l - 1, r)); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}RAddMinQ<ll> は区間加算・区間最小値の遅延評価セグメント木です。apply(l, r, x) と prod(l, r) は 0 始まりの半開区間 を対象にします。
使用ライブラリ:cpp_include@402f0cf