自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

搬运于2025-08-24 23:01:21，当前版本为作者最后更新于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);
}