ABC484 E - Subsegment Sum Finder
- サイト
- AtCoder
- コンテスト
- ABC484
- 問題
- E - Subsegment Sum Finder
- 難易度
- 1159
長さ の数列 について、総和が 以上 以下になる空でない連続部分列の個数を求める問題です。取り出す位置が異なる部分列は区別します()。 には負の値も含まれます。
累積和の差に言い換える
Section titled “累積和の差に言い換える”、 とします。位置 から までの和は なので、条件は
です。
右端 を左から順に処理すると、それまでの累積和 のうち、区間 に入るものの個数を求めればよいです。負の要素があるため累積和は単調とは限りませんが、値ごとの出現回数を管理すれば数えられます。
座標圧縮して区間和を求める
Section titled “座標圧縮して区間和を求める”すべての累積和を座標圧縮し、各値がこれまでに何回現れたかをセグメント木に持ちます。最初に の個数を にします。
現在の累積和を とすると、圧縮した値の列で bisect_left(t - R) から bisect_right(t - L) までの半開区間の個数の和を求めます。上端に bisect_right を使うことで、 と等しい値も含められます。区間の端の値そのものが圧縮対象に含まれていなくても、二分探索で境界を求められます。
個数を答えに加えてから、現在の累積和 の個数を 増やします。問い合わせを先に行うことで、空の部分列を数えず、必ず の組だけを数えられます。同じ累積和が複数回現れる場合も、その出現回数を足すので正しく扱えます。
座標圧縮と各右端の処理を合わせ、計算量は 、空間計算量は です。累積和と答えには 64 bit 整数を使います。
C++
#include "shogo-library/base/all"#include "shogo-library/data_structures/segtree.hpp"#include "shogo-library/utility/compress.hpp"#include "shogo-library/utility/vector_func.hpp"
void solve() { LL(N, L, R); VL(A, N); Compress<ll> C(cumulative_sum(A)); RSumQ<ll> seg(C.size()); seg.apply(C.id(0), 1); ll ans = 0, t = 0; for (ll a : A) { t += a; ans += seg.prod(C.bisect_left(t - R), C.bisect_right(t - L)); seg.apply(C.id(t), 1); } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}自作ライブラリの Compress と SegTree を使っています。cumulative_sum(A) は先頭の を含む累積和を返し、seg.apply(i, 1) は位置 の個数を 増やします。