Petya and Array CodeForces - 1042D【逆序对变形】

题意：

  给出一个 $n$n 个数的数组和一个 $t$t，要求出满足 ∑i=lr​ai​<t 的 $l$l和 $r$r 的对数。

数据范围： $1\le n\le 200,000,\mid t\mid \le 2\cdot 10^{14},\mid a_i\mid \le 10^9$1≤n≤200,000,∣t∣≤2⋅1014,∣ai​∣≤109

思路：

  维护前缀和 $sum\left[i\right]$sum[i] ，对于 1≤j<i，所求即为满足： sum[i]−sum[j]<t的 $(i,j)$(i,j)的数目，转化为： sum[i]−t<sum[j]，就变成了求逆序对问题了。
数据范围比较大，要离散化。

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
typedef long long ll;
ll t,sum[N],tmp[N];
int n;
int bit[N];
void update(int p)
{
    while(p<=n+1)
    {
        bit[p]++;
        p+=(p&-p);
    }
}
ll query(int p)
{
    ll res=0;
    while(p>0)
    {
        res+=bit[p];
        p-=(p&-p);
    }
    return res;
}
int main()
{
    scanf("%d%lld",&n,&t);
    int a;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a);
        sum[i]=sum[i-1]+a;
        tmp[i]=sum[i];
    }
    sort(tmp,tmp+1+n);
    ll ans=0;
    update(lower_bound(tmp,tmp+1+n,0)-tmp+1);
    for(int i=1;i<=n;i++)//离散化
    {//cout<<"sum="<<sum[i]<<" ";
        int pos=lower_bound(tmp,tmp+1+n,sum[i])-tmp+1;//cout<<"pos="<<pos<<" ";
        int tp=upper_bound(tmp,tmp+1+n,sum[i]-t)-tmp+1;//cout<<"tp="<<tp<<" ";
        //cout<<query(n+1)<<" "<<query(tp-1)<<" "<<query(4);
        ans+=(query(n+1)-query(tp-1));//cout<<"ans="<<ans<<endl;
        update(pos);
    }
    printf("%lld\n",ans);
    return 0;
}