题意简述

给定长度为 $n$ 的数组 $a$ 和阈值 $x$。对于每个子段 $[l, r]$，从左到右累加 $a_i$ 到计数器 $g$，若中途 $g > x$ 则将 $g$ 重置为 $0$。求最终 $g \neq 0$ 的子段个数。

关键观察

当遇到某个位置 $i$ 使得前缀和超过 $x$ 时，$g$ 就会清零。此后，该位置右侧的统计相当于从该位置重新开始计数。

我们可以从右往左进行 DP。设 $dp[i]$ 表示从第 $i$ 个蘑菇开始，以它为左端点 $l$，且最终 $g \neq 0$ 的右端点 $r$ 的个数（也就是对所有 $r \ge i$，子段 $[i, r]$ 最后 $g \neq 0$ 的数量）。注意，这里的计数方式依赖于代码中的定义：代码中 $dp[i]$ 实际上统计的是“以 $i$ 开头且最终 $g \neq 0$ 的子段数”，并且利用了前缀和和二分。

推导

令前缀和数组 $p$，其中 $p_i = \sum_{j=1}^{i} a_j$（$p_0=0$）。当我们从位置 $i$ 开始累加时，如果在位置 $q-1$ 处（即 $p_{q-1} - p_{i-1} \le x$）仍满足条件，而在 $q$ 处首次超过 $x$，则游戏会在 $q$ 处清零，后续相当于从 $q+1$ 重新开始。

那么对于左端点 $i$：

• 如果一直累加到末尾都不超过 $x$，则所有右端点 $r \in [i, n]$ 都满足最终 $g \neq 0$，贡献为 $n - i + 1$。
• 否则，设第一个超过 $x$ 的位置为 $q$，那么在 $[i, q-1]$ 范围内的右端点都满足条件，因为在这些右端点处游戏还未清零；而 $q$ 处会清零，之后的情况等价于以 $q+1$ 为起点重新开始。因此有递推关系：$$dp[i] = (q - i) + dp[q+1]$$ 其中 $q$ 是满足 $p_q - p_{i-1} > x$ 的最小位置。

在代码实现中，将 $dp$ 数组倒过来计算，并利用前缀和 $a$（实际代码中 $a$ 被原地改为前缀和）和二分查找 $q$：q = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();（注意这里 $a[i]$ 是前缀和 $p_i$，所以 $a[i] + x$ 对应 $p_i + x$，二分查找第一个 $> p_i + x$ 的位置 $q$）。于是 $dp[i] = dp[q] + q - i - 1$，含义为：从 $i$ 开始，清零发生在 $q$（注意下标换算），$[i, q-1]$ 内的右端点有 $(q - i - 1)$ 个，再加上从 $q$ 开始的后续方案 $dp[q]$。

最终答案就是 $\sum_{i=0}^{n-1} dp[i]$（代码中 $i$ 从 $0$ 到 $n-1$）。

时间复杂度

对每个测试用例，前缀和 $O(n)$，反向遍历 $O(n)$，每次二分 $O(\log n)$，总复杂度 $O(n \log n)$，满足 $\sum n \le 2 \times 10^5$ 的限制。

参考代码

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

using ll = long long;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    int tests;
    cin >> tests;
    while (tests--) {
        int n;
        ll x;
        cin >> n >> x;
        vector<ll> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];
        // 计算前缀和，原地覆盖
        partial_sum(a.begin() + 1, a.end(), a.begin() + 1);
        vector<int> dp(n + 2, 0); // dp[n+1] 默认为0
        for (int i = n - 1; i >= 0; --i) {
            int q = upper_bound(a.begin(), a.end(), a[i] + x) - a.begin();
            dp[i] = dp[q] + q - i - 1;
        }
        cout << accumulate(dp.begin(), dp.begin() + n, 0ll) << '\n';
    }
}