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

>传送门<

前言

这题我前前后后看了三遍，每次都是把网上相关的博客和通过代码认真看了再思考，然并卵，最后终于第三遍也就是现在终于看懂了，其实懂了之后发现其实没有那么难，但是的的确确需要思维。(博客分析那块写的啰里吧嗦又改了很多废话)

题意

在一个长度为$10^{9}$的序列上，保证只有$n(n<10^{6})$个区间等于$1$，且$1$的个数小于10^{7}，其他位置全部为$-1$，求区间和$>0$的区间数量

分析

题目意思很简单，对不对~ 那接下来我们就思考下该怎么做这题。

考虑做前缀和，问题就转化成$sum[i]-sum[j] > 0$的对数

举个栗子，比如序列$\left \{ -1,-1,-1,1,1,1,1 \right \}$，对应的前缀和为$\left \{ -1,-2,-3,-2,-1,0,1 \right \}$

那么$-1>-2$，中间的$\left \{ -1,-1,1,1,1 \right \}$区间和$>0$

由于数据范围较大不可能对整个数组前缀和进行处理，我们注意到能被1覆盖的区间长度最多有$3e7$，因为区间向前，向后最多可以覆盖$1e7$，所以加起来就是$3e7$，这是本题求解的关键。

所以我们可以处理一下区间，让它尽可能的延伸而又不至于小于$0$，之后我们只需要计算在当前点有多少前面点的前缀和小于它就行了。这样我们就可以用树状数组来求，可范围太大了我们只能用别的方法(不甘心的我用树状数组试了下果然超时)

Code

#include<bits/stdc++.h>

typedef long long ll;

using namespace std;

const int maxn = 1e7+;

int l[maxn], r[maxn], n;

int L[maxn],R[maxn];

int num[maxn*];

int main()

{

    scanf("%d", &n);

    for(int i = ; i <= n; i++) scanf("%d%d", &l[i], &r[i]);

    r[] = R[] = -, l[n+] = 1e9;

    int len=;

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

        len += r[i]-l[i]+;

        R[i] = min(r[i]+len,l[i+]-);

        len -= l[i+]-r[i]-;

        if(len<) len=;

    }

    len=;

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

        len += r[i]-l[i]+;

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

        len -= l[i]-r[i-]-;

        if(len<) len=;

    }

    int now = 1e7+;

    num[now] = ;

    ll sum = , ans = ;

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

        for(int j = max(L[i],R[i-]+); j <= R[i]; j++){

            if(j>=l[i]&&j<=r[i]){

                sum += num[now];

                num[++now]++;

            }else{

                sum -= num[--now];

                num[now]++;

            }

            ans += sum;

        }

    }

    printf("%lld",ans);

    return ;

}

/*

now记录的是当前的前缀和，sum记录前缀和小于now的数量，num数组记录的所有前缀和对应的数目。

假如j对应的数字是1，num[++now]显然应该加1，由于此时前缀和比上次要大，那么执行这一步操作前我们应该先把sum加上num[now]；

假如j对应的数字是-1，num[--now]也当然加1，这时候前缀和比上次要小，执行完这步后sum应当减去此时和now相等的前缀和数量就得到比now小的前缀和数量。

*/

可能有的人会跟我有一样的疑惑，一但中间出现“断层”怎么办？也即是中间有非常多的$-1$导致相邻两端不能相连。你仔细想想，其实对于我们这种做法没有任何影响，我们只处理对答案有贡献的区间的点。你可能会说如果”断层“的话前缀和应该重新计算，但是实际上我们是在判断$sum[i]-sum[j] > 0$即$sum[i]>sum[j]$，从不从$0$开始算我们并不关心，我们只在乎他们的相对大小，这里一定要好好想一想！！！

参考资料：

https://www.cnblogs.com/ckxkexing/p/11219612.html

https://blog.csdn.net/qq_41785863/article/details/98469396

https://www.cnblogs.com/bpdwn-cnblogs/p/11252185.html

巴特西

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

最新文章

热门文章