コンテンツにスキップ

AALC001 A - Segment Tree

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

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

  • 1 i x:AiA_i を xx に変更する。
  • 2 l r:min⁡(Al,…,Ar)\min(A_l, \dots, A_r) を出力する。

1 点の更新と区間の最小値の取得なので、最小値を演算とするセグメント木をそのまま使えます。どちらの操作も 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/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 始まりの半開区間 [l,r)[l, r) を対象にするので、prod(l - 1, r) としています。

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