http://codeforces.com/contest/1042/problem/D

题意

给一个数组n个元素，求有多少个连续的子序列的和<t

(1<=n<=200000,abs(a[i])<=1e9)

思路

• 将公式转化以下，sum[r]-sum[l-1]<t 变成 sum[r]<sum[l-1]+t
• 可以考虑遍历每个r,先更新sum[r-1]+t,统计有多少满足条件的sum[l-1],反向树状数组维护即可

实现细节

• 对于每个r是更新他的sum[r-1]
• 因为要统计>sum[r]的数有多少，但是反向树状数组是包含自己当前这个点的，所以要加一
• 反向树状数组的右边界最好是数组大小

#include<bits/stdc++.h>

#define M 400005

#define ll long long

using namespace std;

int tr[M];

int n,tot,i;

ll tp,p[M],x[M],ans,t;

int lowbit(int x){return x&(-x);}

void add(int x){

    while(x>0){

        tr[x]++;x-=lowbit(x);

    }

}

int qy(int x){

    x++;         //

    int ans=0;

    while(x<M){    //

       ans+=tr[x];x+=lowbit(x);

    }

   return ans;

}

int fd(ll x){

    return lower_bound(p,p+tot,x)-p+1;

}

int main(){

    cin>>n>>t;

    tot=0;

    for(i=1;i<=n;i++){

        scanf("%lld",&x[i]);

        x[i]+=x[i-1];

        p[tot++]=x[i];

        p[tot++]=x[i]+t;

    }

    sort(p,p+tot);

    tot=unique(p,p+tot)-p;

    ans=0;

    for(i=1;i<=n;i++){

        add(fd(x[i-1]+t));   //

        ans+=qy(fd(x[i]));

        //cout<<ans<<endl;

    }

    cout<<ans;

}