自动搬运

查看原文

来自洛谷，原作者为

	Register_int 分道扬镳

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