P10162 题解

Register_int · 2024-02-17 19:14:49 · 题解

考虑分治。设当前处理 [l,r]，分治中心为 (p,p+1) 中间那个缝。现在要算出经过分治中心的区间答案之和。

考虑直接以 p 为中心给他切成两部分，那么这两部分就是 [l,p] 的后缀与 [p+1,r] 的前缀。直接预处理出左半边后缀的值与右半边前缀的值，设他们分别为 x_l,x_{l+1},\cdots,x_p 与 y_{p+1},y_{p+2},\cdots,y_r，那么区间 [i,j] 的价值就为 \max(x_i,y_j)。

拆贡献，考虑有多少对区间满足其价值等于 x_i,y_j。先处理是 x 的情况，那么区间个数就是 \le x 的 y 的个数。这是一个二维偏序问题，可以直接将右半部分拍到数轴上做前缀和解决，时间复杂度是 O(n)。用 y 算 x 的部分同理，时间复杂度为离散化的一个 \log，总时间复杂度是 O(n\log^2 n)。由于常数巨小可以通过。

然后事实上你发现第二只 \log 是离散化，那直接从下面两层归并上来就行了。可以做到单 \log。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef unsigned uint;

const int MAXN = 1e6 + 10;

int n, a[MAXN], id[MAXN], t[MAXN], tot;

int b[MAXN]; uint ans, c[MAXN];

void solve(int l, int r) {

    if (l == r) return ;

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

    for (int i = mid, p = -1e18; i >= l; i--) {
        b[i] = max(p, a[i] - a[i + 1]);
        p = max(p, a[i] - max(a[i - 1], a[i + 1]));
    }
    for (int i = mid + 1, p = -1e18; i <= r; i++) {
        b[i] = max(p, a[i] - a[i - 1]);
        p = max(p, a[i] - max(a[i - 1], a[i + 1]));
    }

    tot = 0;
    for (int i = l; i <= r; i++) t[++tot] = b[i];
    sort(t + 1, t + tot + 1), tot = unique(t + 1, t + tot + 1) - t - 1;
    for (int i = l; i <= r; i++) id[i] = lower_bound(t + 1, t + tot + 1, b[i]) - t;

    for (int i = mid + 1; i <= r; i++) c[id[i]]++;
    for (int i = 1; i <= tot; i++) c[i] += c[i - 1];
    for (int i = l; i <= mid; i++) ans += (uint)b[i] * c[id[i]];
    for (int i = 1; i <= tot; i++) c[i] = 0;

    for (int i = l; i <= mid; i++) c[id[i]]++;
    for (int i = 1; i <= tot; i++) c[i] += c[i - 1];
    for (int i = mid + 1; i <= r; i++) ans += (uint)b[i] * c[id[i] - 1];
    for (int i = 1; i <= tot; i++) c[i] = 0;

}

int main() {
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    solve(1, n), printf("%u", ans);
}