AALC001 A - Segment Tree
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- A - Segment Tree
- 難易度
- -
長さ の非負整数列 に対して、次の 2 種類のクエリを合計 個処理する問題です()。
1 i x: を に変更する。2 l r: を出力する。
1 点の更新と区間の最小値の取得なので、最小値を演算とするセグメント木をそのまま使えます。どちらの操作も なので、全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"
void solve() { LL(N, Q); VL(A, N); RMinQ<ll> seg(A); rep(Q) { LL(q); if (q == 1) { LL(i, x); seg.set(i - 1, 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();}RMinQ<ll> は区間の最小値を求めるセグメント木です。prod(l, r) は 0 始まりの半開区間 を対象にするので、prod(l - 1, r) としています。
使用ライブラリ:cpp_include@402f0cf