CF 1994 C. Hungry Games (*1600) 思维+二分

CF 1994 C. Hungry Games (*1600) 思维+二分

题目链接

题意：

给你一个长度为 \(n\) 的关卡，和一个正整数 \(x\)，初始分数为 \(0\)，通过每个关卡就会获得对应的分数。

但是分数如果超过 \(x\)，就会清零。现在让你求出满足最终得分不为零的所有子区间数量。

思路：

正难则反，改求最终得分为零的所有子区间数量。考虑维护前缀和数组，然后枚举左端点。

每次在前缀和数组中查询对应的右端点即可。

代码：

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

void Showball(){
   int n,x;
   cin>>n>>x;
   vector<int> a(n);
   vector<LL> s(n+1);
   for(int i=0;i<n;i++){
     cin>>a[i];
     s[i+1]=s[i]+a[i];
   }
   LL ans=1LL*n*(n+1)/2;
   vector<int> f(n+1);
   for(int i=n-1;i>=0;i--){
    auto p=lower_bound(all(s),s[i]+x+1)-s.begin();
    f[i]=(p==n+1?0:f[p]+1);
    ans-=f[i];
   }
   cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}