P10798 题解

Register_int · 2024-07-21 16:29:56 · 题解

全取绝对值对题目没有影响哎，再离散化，值域变到 1\sim5\times10^5。
把每一种数单独掏出来。设当前有一个正整数序列，满足 A_{k_1}=A_{k_2}=\cdots=A_{k_m}=x,1=k_1<k_2<\cdots<k_m=n，并且所有数都 \le x，怎么让以 x 为左右端点的威胁区间尽可能少呢？设我们将 x 个设为负数，y 个设为正数，那么威胁区间的个数有 \binom x2+\binom y2 个。显然 x,y 要尽可能接近，所以取 x=\left\lfloor\frac m2\right\rfloor,y=\left\lceil\frac m2\right\rceil 即可。
注意一点：当 x=0 时你是没法这样干的，因为 0=-0，不用管他直接算总数就好。
对原序列从前往后扫，记录每个数上一次出现的位置，用 st 表快速计算区间最小值，判断这个区间是不是威胁区间。若是，则将区间内该数的个数加一，否则计算答案并清空。时间复杂度 O(n\log n)。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

int n, m, a[MAXN], b[MAXN], f[20][MAXN];

inline 
int query(int l, int r) {
    int k = __lg(r - l + 1);
    return max(f[k][l], f[k][r - (1 << k) + 1]);
}

int p[MAXN], cnt[MAXN]; ll ans;

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]), a[i] = abs(a[i]);
    memcpy(b, a, sizeof a), sort(b + 1, b + n + 1);
    m = unique(b + 1, b + n + 1) - b - 1;
    for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b;
    for (int i = 1; i <= n; i++) f[0][i] = a[i];
    for (int i = 1; i <= __lg(n); i++) {
        for (int j = 1; j + (1 << i) - 1 <= n; j++) {
            f[i][j] = max(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!p[a[i]]) { p[a[i]] = i; continue; }
        if (query(p[a[i]], i) <= a[i]) cnt[a[i]]++;
        else {
            ll x = cnt[a[i]] + 1 >> 1, y = cnt[a[i]] + 2 >> 1;
            if (b[a[i]]) ans += x * (x - 1) / 2 + y * (y - 1) / 2;
            else ans += (ll)cnt[a[i]] * (cnt[a[i]] + 1) / 2;
            cnt[a[i]] = 0;
        }
        p[a[i]] = i;
    }
    for (int i = 1; i <= m; i++) {
        ll x = cnt[i] + 1 >> 1, y = cnt[i] + 2 >> 1;
        if (b[i]) ans += x * (x - 1) / 2 + y * (y - 1) / 2;
        else ans += (ll)cnt[i] * (cnt[i] + 1) / 2;
    }
    printf("%lld", ans);
}