2019牛客暑期多校训练营（第二场） - J - Go on Strike!

题目链接：https://ac.nowcoder.com/acm/contest/882/C

来自：山东大学FST_stay_night的的题解，加入一些注释帮助理解神仙代码。

好像题解被套了一次又一次

要学习的地方我觉得是2点：

1.使用dp（贪心）的思想求出每段所在的连续段

2.因为前缀和是连续变化的，可以用lazy标记来代替树状数组来维护。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define ERR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }

void err(istream_iterator<string> it) {

    cerr << "\n";

}

template<typename T, typename... Args>

void err(istream_iterator<string> it, T a, Args... args) {

    cerr << *it << "=" << a << ", ";

    err(++it, args...);

}

#define ERR1(arg,n) { cerr<<""<<#arg<<"=\n  "; for(int i=1;i<=n;i++) cerr<<arg[i]<<" "; cerr<<"\n"; }

#define ERR2(arg,n,m) { cerr<<""<<#arg<<"=\n"; for(int i=1;i<=n;i++) { cerr<<"  "; for(int j=1;j<=m;j++)cerr<<arg[i][j]<<" "; cerr<<"\n"; } }

const int INF = 0x3f3f3f3f;

const int MAXN = 10000000, MAXM = 1000000;

int l[MAXM + 5], r[MAXM + 5], f[MAXM + 5], g[MAXM + 5];

int sum[MAXN * 3 + 5], b[MAXN * 3 + 5], c[MAXN * 3 + 5];

int main() {

#ifdef Yinku

    freopen("Yinku.in", "r", stdin);

#endif // Yinku

    int n;

    scanf("%d", &n);

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

        scanf("%d%d", &l[i], &r[i]);

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

    //f[i]以i段右端点为结尾的能构造出的最大的前缀和

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

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

    //0：以i-1段右端点结尾的能构造出的最大的前缀和都不足够跨过[i-1,i]之间的-1

    //f[i - 1] - (l[i] - r[i - 1] - 1)：跨过之后还剩下多少贡献给这段

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

    //g[i]以i段左端点为开头的能构造出的最大的前缀和

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

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

    //ERR1(f, n);

    //ERR1(g, n);

    int i = 1, base = 10000000;

    ll ans = 0;

    while(i <= n) {

        int j = i + 1;

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

            //说明这个[j-1,j]之间的-1段可以因为两侧的f[j-1]和g[j]足够大而连接起来

            j++;

        }

        j--;

        //此时j是从i开始最远能够连接到的区间

        int left = max(0, l[i] - g[i]), right = min(1000000000 - 1, r[j] + f[j]);

        //left,right是至少会产生一个贡献的范围

        //ERR(left, right);

        int t = i, mi = INF, mx = 0;

        sum[0] = 0;

        for(int k = left; k <= right; k++) {

            //统计这一整段可连接区间的前缀和

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

                sum[k - left + 1] = sum[k - left] + 1;

            else

                sum[k - left + 1] = sum[k - left] - 1;

            if(k == r[t])

                t++;

            mi = min(mi, sum[k - left + 1] + base);

            mx = max(mx, sum[k - left + 1] + base);

            //b记录前缀和出现过的次数

            b[sum[k - left + 1] + base] ++;

        }

        //ERR1(sum, right);

        //b记录前缀和出现过的次数的后缀和

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

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

        //包含最左侧点的贡献

        ans += b[base + 1];

        for(int k = left; k <= right; k++) {

            t = sum[k - left + 1] + base;

            //t表示k位置sum的值

            //b[t+1]比t大的值的个数

            //c[t+1]比在k位置左侧的比t大的值的个数的lazy

            b[t + 1] -= c[t + 1]; //把lazy加上去

            c[t] += c[t + 1] + 1; //lazy标记下移

            c[t + 1] = 0; //清空lazy

            ans += b[t + 1];

        }

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

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

        i = j + 1;

    }

    printf("%lld", ans);

    return 0;

}

巴特西

2019牛客暑期多校训练营（第二场） - J - Go on Strike! - 前缀和预处理

最新文章

热门文章