Petya and Array CodeForces

很不错的一道题

给你一个长度为n的数组，问共有多少个区间满足区间之和小于给定的数t

这种题一般做法肯定是枚举，固定左端点枚举右端点，枚举的过程需要优化，否则就是n方

这道题我先求一个前缀和，然后逆着枚举，显然问题转化为了对于一个数，如果寻找他右边的数哪些小于它+t，这就转化为了区间求和，可以树状数组或者线段树，但是数的范围太大，因此需要用离散化

这道题的还有一个问题是定位，有一个很简单的定位方法就是把每一个前缀和+t也放进去，这样去定位就很简单了

另外就是使用upper_bound不过找的数要减一

具体做法看代码

#include<bits/stdc++.h>

using namespace std;

#define endl "\n"

#define pf printf

#define int long long

#define IO ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int maxn=+;

int sum[maxn],a[maxn],up;

vector<int> v;

int n,t;

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

void add(int x,int d)

{

    while(x<=up){

        sum[x]+=d;x+=lowbit(x);

    }

}

int Sum(int x)

{

    int ret=;

    while(x>){

        ret+=sum[x];

        x-=lowbit(x);

    }

    return ret;

}

main()

{

    IO;

    int ans=;

    cin>>n>>t;

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

        cin>>a[i];

        a[i]+=a[i-];

        v.push_back(a[i]);

        if(a[i]<t) ans++;

    }

    sort(v.begin(),v.end());

    v.erase(unique(v.begin(),v.end()),v.end());

    up=v.size();

    for(int i=n;i;i--){

        ans+=Sum(upper_bound(v.begin(),v.end(),a[i]+t-)-v.begin());

        add(lower_bound(v.begin(),v.end(),a[i])-v.begin()+,);

    }

    cout<<ans<<endl;

}

巴特西

Petya and Array CodeForces - 1042D

最新文章

热门文章