【链接】 我是链接,点我呀:)
【题意】
题意
【题解】
把a[i]处理成前缀和
离散化.
枚举i从1..n假设a[i]是区间和的a[r]
显然我们需要找到a[r]-a[l]<t的l的个数
即a[r]<t+a[l]
那么我们处理完每个i之后,每次把a[i]+t加入到树状数组中去。
每次以进入i的时候,找到比a[r]大的a[l]+t的个数就好(用树状数组求和即可)
【代码】
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 2e5;
int n;
ll t;
ll a[N+10];
ll b[N*2+10];
map<ll,int> dic,dic1;
int lowbit(int x){
return x&(-x);
}
ll get_sum(int x){
ll ans = 0;
while (x>0){
ans = ans + b[x];
x = x-lowbit(x);
}
return ans;
}
void add(int x){
while (x<=2*N+2){
b[x]= b[x]+1;
x = x + lowbit(x);
}
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin >> n >> t;
dic[0] = 1;
dic[0+t] = 1;
for (int i = 1;i <= n;i++) {
cin >> a[i];
a[i]+=a[i-1];
dic[a[i]] = 1;
dic[a[i]+t] = 1;
}
int cnt = 0;
for (auto temp:dic){
cnt++;
dic1[temp.first] = cnt;
}
add(dic1[0+t]);
//cout<<dic1[0+t]<<endl;
ll fans = 0;
for (int i = 1;i <= n;i++){
ll temp1 = get_sum(cnt)-get_sum(dic1[a[i]]);
fans = fans + temp1;
add(dic1[a[i]+t]);
}
cout<<fans<<endl;
return 0;
}