树状数组，逆序对——CodeForces - 1042D

#include<stdio.h>
#include<iostream>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=2e5+7;
LL a[maxn],sum[maxn],temp[maxn],c[maxn],t;
int n;
int lowbit(int x){
    return x&(-x);
}
void add(int x){
    while(x<=n+1){
        c[x]++;
        x+=lowbit(x);
    }
}
int ask(int x){
    int ans=0;
    while(x){
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    scanf("%d%lld",&n,&t);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum[i]=sum[i-1]+a[i];
        temp[i]=sum[i];
    }
    sort(temp,temp+1+n);
    LL ans=0;
    for(int i=1;i<=n;i++){
        int pos=lower_bound(temp,temp+1+n,sum[i-1])-temp+1;
        add(pos);
        pos=upper_bound(temp,temp+1+n,sum[i]-t)-temp;
        ans+=i-ask(pos);
    }
    printf("%lld\n",ans);
    return 0;
}