コンテンツにスキップ

AALC001 C - Binary Search on a Segment Tree

サイト
AtCoder
コンテスト
AALC001
問題
C - Binary Search on a Segment Tree
難易度
-

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

  • 1 i x:AiA_i を xx に変更する。
  • 2 l t:∑i=lrAi≥t\sum_{i=l}^{r} A_i \ge t となる rr(l≤r≤Nl \le r \le N)の最小値を出力する。なければ N+1N + 1 を出力する。
  • 3 r t:∑i=lrAi≥t\sum_{i=l}^{r} A_i \ge t となる ll(1≤l≤r1 \le l \le r)の最大値を出力する。なければ 00 を出力する。

和のセグメント木を使います。Ai≥0A_i \ge 0 なので、ll を固定すると ∑i=lrAi\sum_{i=l}^{r} A_i は rr について単調に増えます。そのため、クエリ 2 は「和が tt 未満である間、右に伸ばせるだけ伸ばす」という二分探索で求まります。これはセグメント木上の二分探索(ACL の max_right に当たる操作)で O(log⁡N)O(\log N) で行えます。クエリ 3 も同様に、左に伸ばす二分探索(min_left)で求まります。

全体の計算量は 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);
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 始まりの半開区間 [l−1,r′)[l - 1, r') の和が tt 未満となる最大の r′r' を返します。0 始まりで r′r' 番目(1 始まりで r′+1r' + 1 番目)の要素を加えたときに初めて tt 以上になるので、答えは r′+1r' + 1 です。r′=Nr' = N のときは N+1N + 1 になり、「存在しない」場合の出力とも一致します。
  • min_left(r, f) は、半開区間 [l′,r)[l', r) の和が tt 未満となる最小の l′l' を返します。0 始まりで l′−1l' - 1 番目(1 始まりで l′l' 番目)の要素を加えたときに初めて tt 以上になるので、答えは l′l' です。l′=0l' = 0 のときも、そのまま「存在しない」場合の出力 00 になります。

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