【LOJ2950】「NOIP2018」铺设道路

【题目链接】

• 点击打开链接

【思路要点】

• 有一个显然正确的贪心：处理区间 [ l , r ] [l,r] [l,r] 时，找到区间最小值的位置 m i d mid mid ，对整个区间执行 a m i d a_{mid} amid​ 次操作，并分治到 [ l , m i d − 1 ] , [ m i d + 1 , r ] [l,mid-1],[mid+1,r] [l,mid−1],[mid+1,r] 分别处理。
• 这个结构对应了序列的笛卡尔树，因此构建笛卡尔树计算即可。
• 时间复杂度 O ( N ) O(N) O(N) 。

【代码】

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -f;
	for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
	x *= f;
}
int n, ans, a[MAXN];
int root, top, s[MAXN];
int lc[MAXN], rc[MAXN], fa[MAXN];
int main() {
	freopen("road.in", "r", stdin);
	freopen("road.out", "w", stdout);
	read(n);
	for (int i = 1; i <= n; i++)
		read(a[i]);
	for (int i = 1; i <= n; i++) {
		while (top != 0 && a[i] < a[s[top]]) {
			rc[s[top]] = lc[i];
			lc[i] = s[top--];
		}
		s[++top] = i;
	}
	root = s[1];
	for (int i = 1; i <= top - 1; i++)
		rc[s[i]] = s[i + 1];
	for (int i = 1; i <= n; i++) {
		if (lc[i]) fa[lc[i]] = i;
		if (rc[i]) fa[rc[i]] = i;
	}
	for (int i = 1; i <= n; i++)
		ans += a[i] - a[fa[i]];
	printf("%d\n", ans);
	return 0;
}