题解 | #小红统计区间（easy）#

元素单调性（关键特征）：题目明确保证数组元素 为正整数。这一约束提供了极其重要的性质：区间和具备严格的单调递增性。即若区间 的和满足 ，则对于任何 ，区间 的和必定向基数中累加正数，必然也满足 。

基于“正整数带来的区间和单调性”这一核心特征，采用维护动态边界的滑动窗口是最优算法。不必穷举所有区间的左右端点，而是维护一个动态的可行窗口 。

设定左右边界指针都从数组起始位置 开始。随着右指针 向右扩张，窗口内的元素和不断递增。一旦当前窗口 内的区间和 ，由于后续元素均为正数，固定左端点 的情况下，右端点从 延伸到数组末尾 的所有区间必定都满足条件。

此时，可以直接通过数学计算得出以 为起点的合法区间数量为 ，从而避免了冗余的向右遍历。计算完毕后，安全地收缩左边界 （从总和中减去 ），继续探测下一个左端点是否满足条件。

复杂度分析与方案对比

• 时间复杂度： 左右指针 和 均单向从左向右遍历整个数组。在最坏情况下，每个元素最多被纳入窗口一次（ 指针推进），移出窗口一次（ 指针收缩）。总操作次数与数组规模呈线性关系，达到算法下界。
• 空间复杂度： 辅助空间 除了存储原始输入数组所需的 空间外，算法运行状态仅依赖少量的指针变量和状态累加器，不需要像线段树或树状数组那样开辟额外的辅助数据结构空间。

其他算法对比（前缀和 + 二分查找）： 另一种可行方案是预处理前缀和数组（），枚举左端点 ，并通过二分查找在此单调前缀和数组中寻找第一个满足 的右端点 。该方案虽然也有效，但时间复杂度劣化为 ，且存在二分查找带来的常数级性能开销。在当前约束下，滑动窗口（）在时空效能上处于绝对统治地位。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll k;
    cin >> n >> k;

    vector<ll> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    int l = 0;
    int r;
    ll sum = 0;
    ll ans = 0;
    for (r = 0; r < n; r++) {
        sum += a[r];
        while (l <= r && sum >= k) {
            ans += n - r;
            sum -= a[l];
            l++;
        }
    }

    cout << ans << endl;
}