【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;
}