Enough Array [AtCoder Beginner Contest 130 D]

https://atcoder.jp/contests/abc130/tasks/abc130_d

• しゃくとり法

解説

https://atcoder.jp/contests/abc130/submissions/6000372

微妙に何から手を付ければいいか分からない。
こんなときは全探索対象を探す訳だが、ここにも典型テクがある。
条件を満たす連続する区間を探すときに、左端を全探索して、条件を満たす右端を高速に数え上げるというのがある。
これを使おう。
　
左端を全探索すると、総和がK以上である右端であるかどうかは単調性を持つ。
よって、二分探索によって、境界線を探すことができ、それ以降の右端は全部条件を満たすとして、
その個数を答えに加えていく。
今回は更に、その境界線は左端が大きくなるにつれて、右端も大きくなっていく。
つまり、しゃくとり法が使える。
どちらを使ってもいいし、どっちもできるべきだと思う。
今回はなんとなくしゃくとり法でやる。実際こっちのほうが計算量がいいので。
左端を全探索して、右端をK未満である限り伸ばしていく。
whileを抜けるときには境界線がRにあるので、R, R+1, ..., N-1が条件を満たすので、
(N-1)-R+1=N-Rが条件を満たす組み合わせになるので、これの総和をとると答え。

int N; ll K, A[101010], B[101010];
//---------------------------------------------------------------------------------------------------
ll get(int l, int r) { // [l,r]
	ll res = B[r];
	if (0 < l) res -= B[l - 1];
	return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> K;
	rep(i, 0, N) cin >> A[i];
	
	B[0] = A[0];
	rep(i, 1, N) B[i] = B[i - 1] + A[i];
	
	ll ans = 0;
	int R = 0;
	rep(L, 0, N) {
		chmax(R, L);
		while (R < N and get(L, R) < K) R++;
		ans += N - R;
	}
	cout << ans << endl;