// 做出来是证明你会的,一个充分条件。
可能写的有点啰嗦,少侠我相信你,慢慢品味,必然有所得。
错误原因:学过dp,但是这题没有想着用dp。同时也不知道可以这样做。这题也是给我小刀啦皮鼓(开眼了)。之前也是见过,逆向者dp的。真的感觉好神奇啊。(明明就是一个破数组,一个破循环,为啥那么牛呀-_-)
思路:设dpi,为当前下标的所有可行方案数量。我们需要寻找到第一个j使得a【j】> a【i】+ x,这样 i 到 j - 1 就是可行的方案(为什么不找满足的,也可以,但是麻烦,就直接找下一个,这样方便二分查找)(dp一般有2中遍历方式(我知道的)),正着遍历和倒着遍历,尝试着正着遍历,试着想想,想啊想,想不到。完蛋了。
莫急莫急,还有备用方案倒着遍历。设 dp[i] - 左边界位于 i 的良好子段的数目。我们从 dp 开始数起,每数到 i ,我们就要找到一个最小值 j ,使得子段 [i;j] 上的和大于 x 。如果没有这样的 j ,那么所有右界都是好的,否则就是 dp[i]=dp[j+1]+j−i。要搜索 ,我们可以对前缀和进行二进制搜索。答案将是所有 dp 的和。注意这里的:dp【i】 = dp【j+1】+ j - i ;(自古以来dp的递推式子是个难点)。
我们来解释一下:注意一开始我们设dpi为从i开始的所有答案。从后往前推,一开始dp的值必然是0,然后按照我们尝试的dp递推式运行,j - 1 是最后一个满足条件的下标,减去i也就是除了i之外满足条件的个数(这必然是答案的一部分)(注意,取j的时候因为它是第一个大于a【i】+ x的,所以,这里的值按照题目是归零的,所以到 j 的下一个也就是 j+1,这一部分如果满足条件的话也是可以加上的,所以最终答案是)dp【i】 = dp【j+1】+ j - i;
注意点1:dp数组设置大小为n+2,因为这样的话下标最大的是n+1。(二分查找的时候,如果没有找到会返回,an的下一个迭代器,和初始迭代器作差之后,就是n+1,防止越界必须开到有下标n+1的dp数组)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int, int> pii;
typedef pair<ll, ll> PII;
#define pb emplace_back
//#define int ll
#define all(a) a.begin(),a.end()
#define x first
#define y second
#define ps push_back
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
void solve();
const int N = 1e6 + 10;
signed main() {
IOS;
ll t;
cin >> t;
while(t--)
solve();
return 0;
}
void solve() {
ll n;
ll xx;
cin >> n >> xx;
vector<ll> a(n+1,0);
for(int i = 1; i <= n; ++i) cin >> a[i];
partial_sum(a.begin()+1,a.end(),a.begin()+1);
// 因为二分呢
vector<ll> dp(n+2,0);
for(int i = n - 1; i >= 0; -- i)
{
ll q = upper_bound(a.begin(),a.end(),a[i]+xx) - a.begin();// j + 1
dp[i] = dp[q] + q - 1 - i;
}
// ll sum = 0;
// for(auto it : dp) sum += it;
// cout << sum << endl;
// 最后求和的函数就是,上面3行可以直接用一句话代替。
// 分为3个参数,起始和终止的迭代器,最后一个是初始值
cout << accumulate(dp.begin(),dp.end(),0LL) << endl;
}