SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R
- サイト
- SamCoding
- コンテスト
- SamCoding Round 7 (Div. 2)
- 問題
- I - Subarrays in Range L-R(常設版)
長さ の数列 と整数 が与えられます。連続する部分列のうち、総和が 以上 以下のものの個数を求める問題です(、、)。 は負になることもあります。
累積和を 、 とすると、区間 の総和は です。条件 を について書き直すと
です。したがって、各 について「 で が に入るものの個数」を足し合わせれば答えになります。
が負になることもあるので は単調ではなく、しゃくとり法は使えません。そこで の順に見ていき、それまでに出てきた を、値ごとの個数として管理します。必要な操作は次の 2 つです。
- を 1 個追加する
- 値が の範囲にある の個数を数える
の値は最大 程度と大きいので、 を座標圧縮して添字にし、区間和を求めるセグメント木(または BIT)で管理します。値の範囲 は、圧縮後の添字では二分探索で求まります。全体で です。
C++(セグメント木)
#include "ou-library/segtree.hpp"#include "sh-library/base/all"
void solve() { LL(N, L, R); VL(A, N); ll t = 0; sl s; s.insert(t); for (ll a : A) { t += a; s.insert(t); } vl v(all(s)); RSumQ<ll> seg(v.size()); ll ans = 0; t = 0; seg.apply(bisect_left(v, t), 1); for (ll a : A) { t += a; ans += seg.prod(bisect_left(v, t - R), bisect_right(v, t - L)); seg.apply(bisect_left(v, t), 1); } print(ans);}
int main() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); solve();}前半では累積和の値を std::set に入れ、ソート済みで重複のない v にしています(座標圧縮)。値 の添字は bisect_left(v, x) です。
後半では t が で、seg.prod(bisect_left(v, t - R), bisect_right(v, t - L)) が「値が にある の個数」です。数えてから seg.apply(..., 1) で を追加するので、 のものだけが数えられます。RSumQ は区間和のセグメント木です。
使用ライブラリ:cpp_include@6c2f83f
Python(BIT)
from bisect import bisect_left, bisect_rightfrom itertools import accumulate
N, L, R = map(int, input().split())A = list(map(int, input().split()))S = [0, *accumulate(A)]v = sorted(set(S))M = len(v)bit = [0] * (M + 1)
def add(i): i += 1 while i <= M: bit[i] += 1 i += i & -i
def count(i): res = 0 while i: res += bit[i] i -= i & -i return res
ans = 0add(bisect_left(v, 0))for t in S[1:]: ans += count(bisect_right(v, t - L)) - count(bisect_left(v, t - R)) add(bisect_left(v, t))print(ans)C++ 版と同じ処理を BIT で書いています。count(i) は添字が 未満の個数なので、2 つの差が範囲内の個数になります。