2场 J -Subarray

题意：

长度为1e91e9的(1,−1)(1,−1)序列，下标从00到1e9−11e9−1，已知有nn个区间为11，其他为−1−1，问存在多少个区间的和>1>1（保证∑1≤i≤nr[i]−l[i]+1≤1e7∑1≤i≤nr[i]−l[i]+1≤1e7）.

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

题解

可能作为区间端点的点个数最多为3e73e7
f[i]表示以第ii个区间右端点为答案右端点的最大区间和
g[i]表示以第ii个区间左端点为答案左端点的最大区间和
f[i]=max(0,f[i−1]−(l[i]−r[i−1]−1))+r[i]−l[i]+1
g[i]=max(0,g[i+1]−(l[i+1]−r[i]−1))+r[i]−l[i]+1
如果f[i]+g[i+1]≥l[i+1]−r[i]−1，说明答案的左右端点可以跨越[r[i]+1,l[i+1]−1]，那么把这些合并考虑
搞完上面，问题就变成了给你一个长度不超过3e7的（1，−1）序列，问有多少区间和大于1
树状数组时间O(n∗logn)，稳T
考虑优化：
很好用的性质：每次查询与上次查询的差距等于1
从左到右枚举左端点，统计右边比当前值大的个数
加个标记，标记左移，稳

#include <iostream>

using namespace std;

const int N = 1e6 + ;

const int M = 4e7 + ;

typedef long long ll;

int l[N], r[N], L[N], R[N];

ll num[M];

int main() {

    int n;

    cin >> n;

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

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

    }

    l[] = r[] = L[] = R[] = -, l[n + ] = r[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 = 2e7 + ;

    ll sum = ;

    num[now] = ;

    ll 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;

        }

    }

    cout << ans << endl;

    return ;

}

团队通过代码

参考博客：

https://blog.csdn.net/qq_40791842/article/details/96736137

https://blog.csdn.net/qq_40871466/article/details/97104326

https://blog.csdn.net/toohandsomeieaseid/article/details/98848517

https://www.cnblogs.com/Yinku/p/11221494.html

https://www.cnblogs.com/wmj6/p/11288038.html

巴特西

2场 J -Subarray

最新文章

热门文章