コンテンツにスキップ

AALC001 B - Lazy Segment Tree

サイト
AtCoder
コンテスト
AALC001
問題
B - Lazy Segment Tree
難易度
-

長さ NN の非負整数列 AA に対して、次の 2 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 l r x:Al,…,ArA_l, \dots, A_r のそれぞれに xx を足す。
  • 2 l r:min⁡(Al,…,Ar)\min(A_l, \dots, A_r) を出力する。

区間への加算と区間の最小値の取得なので、遅延評価セグメント木を使います。区間 [l,r][l, r] の全要素に xx を足すと、その区間の最小値もちょうど xx 増えます。そのため、各ノードには「担当区間の最小値」だけを持たせ、作用は「xx を足す」、作用の合成は「足す値の和」とすればよいです。

どちらの操作も O(log⁡N)O(\log N) なので、全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

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 始まりの半開区間 [l,r)[l, r) を対象にします。

使用ライブラリ:cpp_include@402f0cf