CF817D Imbalanced Array

链接

CF817D Imbalanced Array

题目大意

求：

\[\sum_{l=1}^n\sum_{r=l}^n\left(\max_{i=l}^r\{a_i\}-\min_{i=l}^r\{a_i\}\right) \]

思路

方法一

\(\mathcal{O}(n^3)\) 暴力。

方法二

先转化：

\[\begin{aligned} \sum_{l=1}^n\sum_{r=l}^n\left(\max_{i=l}^r\{a_i\}-\min_{i=l}^r\{a_i\}\right)=\sum_{l=1}^n\sum_{r=l}^n\max_{i=l}^r\{a_i\}-\sum_{l=1}^n\sum_{r=l}^n\min_{i=l}^r\{a_i\} \end{aligned} \]

然后考虑用单调栈优化：对于最大和最小分别开两个单调栈，分别记录若当前点为区间最大或最小的值，那么左右分别到哪个点，即找某个点左边、右边第一个比它大（或小）的值。

然后就能 \(\mathcal{O}(n)\) 做了。

代码

const int N = 1e6 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

ll n, a[N], qx[N], qn[N], tx, tn, f[N], g[N];
ll ans;

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	n = Read();
	for (int i = 1; i <= n; i++) a[i] = Read();
	for (int i = 1; i <= n; i++) {
		for (; tx && a[qx[tx]] <= a[i]; tx--);
		for (; tn && a[qn[tn]] >= a[i]; tn--);
		qx[++tx] = i, qn[++tn] = i;
		f[i] = i - qx[tx - 1];
		g[i] = i - qn[tn - 1];
	}
	tx = tn = 0;
	qx[0] = qn[0] = n + 1;
	for (int i = n; i; i--) {
		for (; tx && a[qx[tx]] < a[i]; tx--);
		for (; tn && a[qn[tn]] > a[i]; tn--);
		qx[++tx] = i, qn[++tn] = i;
		ans += a[i] * (qx[tx - 1] - i) * f[i] - a[i] * (qn[tn - 1] - i) * g[i];
	}
	printf ("%lld\n", ans);
	return 0;
}