AALC001 C - Binary Search on a Segment Tree
- サイト
- AtCoder
- コンテスト
- AALC001
- 問題
- C - Binary Search on a Segment Tree
- 難易度
- -
長さ の非負整数列 に対して、次の 3 種類のクエリを合計 個処理する問題です()。
1 i x: を に変更する。2 l t: となる ()の最小値を出力する。なければ を出力する。3 r t: となる ()の最大値を出力する。なければ を出力する。
和のセグメント木を使います。 なので、 を固定すると は について単調に増えます。そのため、クエリ 2 は「和が 未満である間、右に伸ばせるだけ伸ばす」という二分探索で求まります。これはセグメント木上の二分探索(ACL の max_right に当たる操作)で で行えます。クエリ 3 も同様に、左に伸ばす二分探索(min_left)で求まります。
全体の計算量は です。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"
void solve() { LL(N, Q); VL(A, N); RSumQ<ll> seg(A); rep(Q) { LL(q); if (q == 1) { LL(i, x); seg.set(i - 1, x); } else if (q == 2) { LL(l, t); print(1 + seg.max_right(l - 1, [t](ll a) { return a < t; })); } else { LL(r, t); print(seg.min_left(r, [t](ll a) { return a < t; })); } }}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}RSumQ<ll> は区間和のセグメント木で、max_right と min_left は ACL と同じ仕様です。
max_right(l - 1, f)は、0 始まりの半開区間 の和が 未満となる最大の を返します。0 始まりで 番目(1 始まりで 番目)の要素を加えたときに初めて 以上になるので、答えは です。 のときは になり、「存在しない」場合の出力とも一致します。min_left(r, f)は、半開区間 の和が 未満となる最小の を返します。0 始まりで 番目(1 始まりで 番目)の要素を加えたときに初めて 以上になるので、答えは です。 のときも、そのまま「存在しない」場合の出力 になります。
使用ライブラリ:cpp_include@402f0cf