2019牛客暑期多校训练营（第二场）J.Subarray

题意：给你一个n 表示有n段连续的1序列现在问你在总长度为0~1e9-1的范围内有多少个大于0的子段

思路:假设我们统计了当前的前缀和我们显然可以用树状数组维护一下前缀和这样我们可以nlogn算出答案但是对于1e7的数据这样处理肯定会超时所以我们考虑前缀和是一个每次变化都是1的折线

我们可以直接数组模拟lazy来求出答案

#include <bits/stdc++.h>

using namespace std;

const int N = 1e7+;

const int inf = 0x3f3f3f3f;

typedef long long ll;

const ll mod = 1e7+;

int l[N],r[N];

int f[N],g[N],sum[*N];

int b[*N],c[*N];

int main(){

    ios::sync_with_stdio(false);

    cin.tie(); cout.tie();

    int n; cin>>n;

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

        cin>>l[i]>>r[i];

    }

    f[]=r[]-l[]+;

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

        f[i]=max(r[i]-l[i]+,f[i-]-(l[i]-r[i-]-)+r[i]-l[i]+);

    g[n]=r[n]-l[n]+;

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

        g[i]=max(r[i]-l[i]+,g[i+]-(l[i+]-r[i]-)+r[i]-l[i]+);

    int i=; int now=1e7;

    ll ans=;

    while(i<=n){

        int j=i+;

        while(j<=n&&g[j]+f[j-]>=(l[j]-r[j-]-)){

            j++;

        }

        j--;

        int le=max(,l[i]-g[i]); int ri=min(int(1e9)-,r[j]+f[j]);

        int t=i; int mx,mi; mx=-; mi=inf;

        for(int k=le;k<=ri;k++){

            if(k>=l[t]&&k<=r[t])

                sum[k-le+]=sum[k-le]+;

            else

                sum[k-le+]=sum[k-le]-;

            if(k==r[t]) t++;

            mx=max(mx,sum[k-le+]+now);

            mi=min(mi,sum[k-le+]+now);

            b[sum[k-le+]+now]++;

        }

        for(int k=mx-;k>=mi;k--)

            b[k]+=b[k+];

        ans+=b[now+];

        for(int k=le;k<=ri;k++){

            t=sum[k-le+]+now;

            b[t+]-=c[t+];

            c[t]+=c[t+]+;

            c[t+]=;

            ans+=b[t+];

        }

        for(int k=mi;k<=mx;k++)

            b[k]=,c[k]=;

        i=j+;

    }

    cout<<ans<<endl;

}

巴特西

2019牛客暑期多校训练营（第二场）J.Subarray

最新文章

热门文章