题解 CF1042D 【Petya and Array】

CreeperLordVader · 2019-04-13 19:59:33 · 题解

居然没有权值线段树解法！！！

那我来一个

本题细节真的巨多，思路1分钟，代码5小时。。。

首先，为了能O(1)求出区间和，我们对原序列前缀和并记为序列a

然后考虑题设限制

求有多少个区间[l,r]满足sum(l,r)<t

由于前缀和的存在,sum(l,r)=a(r)-a(l-1)<t

于是变成了a(r)<a(l-1)+t

于是可以扫描一遍a,在每个前缀l处我们只需求出有多少数r满足上式

可以用权值线段树来维护,只需求出a(l-1)+t的排名即可,对应到线段树上就是求出区间和

由于求的前缀不包括l-1自身,所以还要在进入下一个前缀前删除下一个前缀

因为数很大,需要离散化,具体实现略微复杂

我最开始的时候右儿子打成左儿子,调了一小时,后来离散化以后没开long long又花了几小时...

#include<bits/stdc++.h>
#define ll long long
#define update(o) sz[o]=sz[o<<1]+sz[o<<1|1]
using namespace std;
const int MAXN=200005;
ll val[200005];
int cnt[200005];
int n,m;;
ll ans;
ll pref;
ll t,a[200005];
ll num[200005];
int id[200005];
int sz[MAXN<<2];
map<ll,int>times;
template<typename type>
void read(type& x)
{
    char c=getchar();
    int f=1;x=0;
    while(c<'0'||c>'9')
    {
        if(c=='-')f*=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    x*=f;
}
void build(int o,int l,int r)
{
    if(l==r)
    {
        sz[o]=cnt[l];
        return ;
    }
    int mid=(l+r)>>1;
    build(o<<1,l,mid);
    build(o<<1|1,mid+1,r);
    update(o);
}
int query(int o,int l,int r,int k)
{
    if(!k)return 0;
    if(r<=k)
    {
        return sz[o];
    }
    int mid=(l+r)>>1,sum=0;
    sum+=query(o<<1,l,mid,k);
    if(k>mid)sum+=query(o<<1|1,mid+1,r,k);
    return sum;
}
void remove(int o,int l,int r,int k)
{
    if(l==r)
    {
        sz[o]--;
        return ;
    }
    int mid=(l+r)>>1;
    if(k<=mid)remove(o<<1,l,mid,k);
    else remove(o<<1|1,mid+1,r,k);
    update(o);
}
int main()
{
    read(n);
    read(t);
    for(int i=1;i<=n;i++)
    {
        read(num[i]);
        a[i]=a[i-1]+num[i];
        times[a[i]]++;
    }
    sort(a+1,a+n+1);
    m=unique(a+1,a+n+1)-a-1;
    for(int i=0;i<m;i++)
    {
        val[i+1]=a[i+1];
        cnt[i+1]=times[a[i+1]];
    }
    build(1,1,m);
    for(int i=0;i<n;i++)
    {
        pref+=num[i];
        int k=lower_bound(val+1,val+m+1,pref+t-1)-val;
        if(k>m)k=m;
        if(val[k]>=pref+t)k--;
        if(k)ans+=(ll)query(1,1,m,k);
        int p=lower_bound(val+1,val+m+1,pref+num[i+1])-val;
        remove(1,1,m,p);
    }
    printf("%lld\n",ans);
}