BZOJ3745 / SP22343 NORMA2 - Norma 分治，CDQ分治

要命的题目。

写法：分类讨论进行计算。

枚举过每一个\(mid\)的所有区间。对于左端点\(i∈[l, mid - 1]\)，向左推并计算\([l,mid]\)范围内的最大\(/\)最小值。

然后右端点\(p\)分三种类型考虑。

\(p∈[mid + 1, p1 - 1]\)，其中\(p1\)是第一次出现比\(maxw\)大或者比\(minw\)小的数的位置。
\(p∈[p1, p2 - 1]\)，其中\(p2\)是第二次出现比\(maxw\)大或者比\(minw\)小的数的位置。
\(p∈[p2, r]\)，\(r\)是当前枚举区间的右端点。

其中情况一高斯求和，情况二和情况三可以化为前缀最大最小值之和\(/\)积带几个系数的形式\(O(N)\)维护。

要命原因：取膜。

两年\(OI\)一场空，_______。

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 500000 + 5;

const LL Mod = 1000000000;

#define min(x,y) (x < y ? x : y)

#define max(x,y) (x > y ? x : y)

#define mul(x,y) ((1ll * (x % Mod) * (y % Mod)) % Mod)

#define add(x,y) ((0ll + (x % Mod) + (y % Mod)) % Mod)

int n, arr[N]; LL ans;

int _maxw[N], _minw[N];

LL mn1[N], mn2[N], mx1[N], mx2[N], mnmx1[N], mnmx2[N];

int get_maxp (int w, int l, int r) {

    if (_maxw[r] <= w) return r + 1;

    while (l < r) {

        int mid = (l + r) >> 1;

        if (_maxw[mid] > w) {

            r = mid;

        } else {

            l = mid + 1;

        }

    }

    return r;

} 

int get_minp (int w, int l, int r) {

    if (_minw[r] >= w) return r + 1;

    while (l < r) {

        int mid = (l + r) >> 1;

        if (_minw[mid] < w) {

            r = mid;

        } else {

            l = mid + 1;

        }

    }

    return r;

}

void cdq (int l, int r) {

    if (l == r) {

        ans = add (ans, mul (arr[l], arr[r]));

        return;

    }

    int mid = (l + r) >> 1;

    cdq (l, mid + 0);

    cdq (mid + 1, r);

    int maxw = arr[mid], minw = arr[mid];

    mx1[mid - 1] = mx2[mid - 1] = 0;

    mn1[mid - 1] = mn2[mid - 1] = 0;

    mnmx1[mid - 1] = mnmx2[mid - 1] = 0;

    _maxw[mid] = _minw[mid] = arr[mid];

    for (int i = mid + 1; i <= r; ++i) {

        _maxw[i] = max (_maxw[i - 1], arr[i]);

        _minw[i] = min (_minw[i - 1], arr[i]);

    }

    for (int p = mid; p <= r; ++p) {

        mx1[p] = add (mx1[p - 1], mul (_maxw[p], (p + 1)));

        mx2[p] = add (mx2[p - 1], _maxw[p]);

        mn1[p] = add (mn1[p - 1], mul (_minw[p], (p + 1)));

        mn2[p] = add (mn2[p - 1], _minw[p]);

        mnmx1[p] = add (mnmx1[p - 1], mul (_maxw[p], mul (_minw[p], (p + 1))));

        mnmx2[p] = add (mnmx2[p - 1], mul (_maxw[p], _minw[p]));

    }

    for (int i = mid; i >= l; --i) {

        maxw = max (maxw, arr[i]);

        minw = min (minw, arr[i]);

        int p1 = get_maxp (maxw, mid + 1, r); // [mid + 1, r]内第一个比maxw大的地方

        int p2 = get_minp (minw, mid + 1, r); // [mid + 1, r]内第一个比minw小的地方

        if (p1 > p2) swap (p1, p2); // 不关注大小，主要看划分

//		cout << p1 << " " << p2 << endl;

        ans = add (ans, mul (1ll * (p1 - mid - 1) * (p1 + mid - i * 2 + 2) / 2, mul (minw, maxw))); // Part 1

        if (arr[p1] > maxw) {

            ans = add (ans, mul (minw, add (add (mx1[p2 - 1], -mx1[p1 - 1]), -mul (i, add (mx2[p2 - 1], -mx2[p1 - 1])))));

        } else {

            ans = add (ans, mul (maxw, add (add (mn1[p2 - 1], -mn1[p1 - 1]), -mul (i, add (mn2[p2 - 1], -mn2[p1 - 1])))));

        }

        if (p2 <= r) {

            ans = add (ans, add (add (mnmx1[r], -mnmx1[p2 - 1]), -mul (i, add (mnmx2[r], -mnmx2[p2 - 1]))));

        }

    }

}

signed main () {

//	freopen ("data.in", "r", stdin);

    cin >> n;

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

        cin >> arr[i];

    }

    cdq (1, n);

//	cout << ans << endl;

    cout << (((ans % Mod) + Mod) % Mod) << endl;;

}

巴特西

BZOJ3745 / SP22343 NORMA2 - Norma 分治，CDQ分治

最新文章

热门文章