初赛第三大题专项训练

共42道题，当前是第30题

初赛真题

（尺取法求区间个数）给 $n$ 个非负整数 $a[1],a[2], \dots ,a[n]$ ，求区间和小于或等于 $k$ 的区间个数，即求使 $SUM = a[L]+a[L+1]+ \dots +a[R-1]+a[R] <= k$ 的区间 $[L,R]$ 的个数，但由于对内存和复杂度有要求，本题已经用尺取法写好部分代码，请补全程序。

输入第一行两个整数 $n,k(1 \leq n \leq 10^6, 0 \leq k \leq 10^{15})$ 。第二行为 $n$ 个数，表示 $a[i] \sim a[n] (0 \leq a[i] \leq 10^9)$ 的值。

#include <bits/stdc++.h>

#define ll long long
using namespace std;
const int mx = 1e6 + 10;
int n, a[mx];
ll k, sum, ans;
int main() {
	scanf(" %d%lld", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &a[i]);
	}
	int r = 0;
	for (int i = 1; i <= n; ++i) {
		while (r < n) {
			if (___(1)___)
				___(2)___;
			else
				break;
		}
		___(3)___;
		if (i <= r)
			___(4)___;
		else
			___(5)___;
	}
	printf("%lld\n", ans);
	return 0;
}

Question

1. (1) 处应填 ( )。

2. (2) 处应填 ( )。

3. (3) 处应填 ( )。

4. (4) 处应填 ( )。

5. (5) 处应填 ( )。