コンテンツにスキップ

ABC484 E - Subsegment Sum Finder

サイト
AtCoder
コンテスト
ABC484
問題
E - Subsegment Sum Finder
難易度
1159

長さ NN の数列 AA について、総和が LL 以上 RR 以下になる空でない連続部分列の個数を求める問題です。取り出す位置が異なる部分列は区別します(N≤3×105N\le3\times10^5)。AA には負の値も含まれます。

P0=0P_0=0、Pj=A1+⋯+AjP_j=A_1+\cdots+A_j とします。位置 i+1i+1 から jj までの和は Pj−PiP_j-P_i なので、条件は

L≤Pj−Pi≤R⟺Pj−R≤Pi≤Pj−LL\le P_j-P_i\le R \quad\Longleftrightarrow\quad P_j-R\le P_i\le P_j-L

です。

右端 jj を左から順に処理すると、それまでの累積和 P0,…,Pj−1P_0,\dots,P_{j-1} のうち、区間 [Pj−R,Pj−L][P_j-R,P_j-L] に入るものの個数を求めればよいです。負の要素があるため累積和は単調とは限りませんが、値ごとの出現回数を管理すれば数えられます。

すべての累積和を座標圧縮し、各値がこれまでに何回現れたかをセグメント木に持ちます。最初に P0=0P_0=0 の個数を 11 にします。

現在の累積和を tt とすると、圧縮した値の列で bisect_left(t - R) から bisect_right(t - L) までの半開区間の個数の和を求めます。上端に bisect_right を使うことで、t−Lt-L と等しい値も含められます。区間の端の値そのものが圧縮対象に含まれていなくても、二分探索で境界を求められます。

個数を答えに加えてから、現在の累積和 tt の個数を 11 増やします。問い合わせを先に行うことで、空の部分列を数えず、必ず i<ji<j の組だけを数えられます。同じ累積和が複数回現れる場合も、その出現回数を足すので正しく扱えます。

座標圧縮と各右端の処理を合わせ、計算量は O(Nlog⁡N)O(N\log N)、空間計算量は O(N)O(N) です。累積和と答えには 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) は先頭の 00 を含む累積和を返し、seg.apply(i, 1) は位置 ii の個数を 11 増やします。