自动搬运

查看原文

来自洛谷，原作者为

	D2T1 没复活就是似了 | 头发绿绿戴个帽帽，脑袋大大，喜欢唱唱

搬运于2025-08-24 22:54:21，当前版本为作者最后更新于2023-12-22 22:58:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

P10067 [CCO2023] Real Mountains

设 $b_i=\min(\max_{1\leq j\leq i}\{a_j\},\max_{i\leq j\leq n}\{a_j\})$，显然有 $b$ 是一组最小的可达的满足要求的方案。可以证明 $b$ 是唯一的一组方案。所以我们的目标就变为求得最小代价使得 $h$ 变为 $b$。

容易猜测一个结论：每次选择 $h_i$ 最小且需要增加的位置，然后进行一次操作对其 $+1$。显然这个结论是正确的，证明可以考虑若存在 $h_j>h_i$ 且 $j$ 的操作在 $i$ 前，两个交换一定不劣。那么如果有若干个 $h_i$ 并列最小值怎么办？

假设这个并列最小值为 $x$，有 $k$ 个，我们要将这些全部变为 $x+1$。设最左侧的 $x$ 为 $h_l$，最右侧的 $x$ 为 $h_r$。

最优操作方案是：对于左端点，我们找到二元组 $(o,p)$，满足 $h_o>h_l<h_p,o<l<p$，且不存在 $h_l<h_{o'}<h_o,o'<l$，也不存在 $h_l<h_{p'}<h_p,p'>l$。对于右端点，同理找到一个二元组 $(q,r)$。

那么可以先进行一次 $(o,l,p)$，一次 $(l,r,q)$，$(k-2)$ 次 $(l,i,r)$ 完成目标。总代价为 $h_o+h_r+h_p+2k-3+3(k-1)x$。若 $h_p>h_q$，还可以先操作右端点再操作左端点。故最优的总代价为 $h_o+\min(h_p,h_q)+h_r+2k-3+3(k-1)x$。

所以我们得到了一个暴力做法：遍历整个数组，提取出若干个 还需增加的并列最小值，找到两个二元组进行更新。复杂度爆炸。

考虑离散化。若出现在 $h$ 中且大于最小值 $x$ 的数为 $y$，则一定会使用相同的两个二元组更新相同数量、位置的 $x$ 一路到 $y$。所以我们将三元组 $(h_i,i,-1),(b_i,i,1)$ 进行排序然后扫描线，可以将复杂度优化到 $O(n^2)$。

现在问题转化为了一个序列 $h$，两种操作：

• 查询前缀/后缀中大于某值的最小值；
• 一个抽象的修改操作。

发现很难处理修改。然而仔细分析可以发现修改是不需要的。因为根据上述算法，不可能存在两个位置 $(i,j)$，最开始 $h_i<h_j$，在 中途的某个过程时既有 $h_j<b_j$ 又有 $h_i>h_j$。所以只用维护查询操作，使用主席树即可。

const int N = 1e6 + 10;
const ll P = 1e6 + 3;
int n;
ll a[N], b[N];
tuple<ll, int, int> q[N*2];
ll ans;

ll Sum(ll x, ll y){
	return (y * (y-1) / 2 % P - x * (x-1) / 2 % P + P) % P;
}

int t[N*100], ls[N*100], rs[N*100];
int rtl[N], rtr[N], cnt;
int add(int p, int l, int r, int x){
	++ cnt;
	tie(t[cnt], ls[cnt], rs[cnt]) = tie(t[p], ls[p], rs[p]);
	p = cnt;
	if(l == r){
		++ t[p];
	} else {
		int mid = l + r >> 1;
		if(x <= mid){
			ls[p] = add(ls[p], l, mid, x);
		} else {
			rs[p] = add(rs[p], mid+1, r, x);
		}
		t[p] = t[ls[p]] + t[rs[p]];
	}
	return p;
}
int qry(int p, int l, int r, int ge){
	if(t[p] == 0 || r <= ge){
		return -1;
	} else if(l == r){
		return l;
	} else {
		int mid = l + r >> 1, tmp;
		if((tmp = qry(ls[p], l, mid, ge)) > ge){
			return tmp;
		} else {
			return qry(rs[p], mid+1, r, ge);
		}
	}
}

int qrl(int x, int mn){
	return qry(rtl[x], 1, 1e9, mn);
}
int qrr(int x, int mn){
	return qry(rtr[x], 1, 1e9, mn);
}

void solve(){
	scanf("%d", &n);
	for(int i = 1; i <= n; ++ i){
		scanf("%lld", &a[i]);
		q[i] = { a[i], i, -1 };
	}
	ll mx = 0;
	rtl[0] = ++ cnt;
	for(int i = 1; i <= n; ++ i){
		mx = max(mx, a[i]);
		rtl[i] = add(rtl[i-1], 1, 1e9, a[i]);
		b[i] = mx;
	}
	mx = 0;
	rtr[n+1] = ++ cnt;
	for(int i = n; i >= 1; -- i){
		mx = max(mx, a[i]);
		b[i] = min(b[i], mx);
		rtr[i] = add(rtr[i+1], 1, 1e9, a[i]);
		q[i+n] = { b[i], i, 1 };
	}
	sort(q + 1, q + n + n + 1);
	set<int> st;
	for(int i = 1; i < n + n; ++ i){
		if(get<2>(q[i]) == -1){
			st.insert(get<1>(q[i]));
		} else {
			st.erase(get<1>(q[i]));
		}
		if(get<0>(q[i]) != get<0>(q[i+1]) && st.size()){
			ll fr = get<0>(q[i]), to = get<0>(q[i+1]);
			ll l = *st.begin(), r = *st.rbegin(), k = st.size();
			ll oo = qrl(l, fr), pp = qrr(l, fr), qq = qrl(r, fr), rr = qrr(r, fr);
			ll p = qrl(l, fr), q = qrr(r, fr);
			if(k == 1){
				ans += Sum(fr, to);
				ans += (oo + pp) % P * (to - fr) % P;
			} else {
				ans += (oo + rr + min(pp, qq) + k + k - 3) % P * (to - fr) % P;
				ans += 3 * (k - 1) % P * Sum(fr, to) % P;
			}
			ans %= P;
		}
	}
	printf("%lld\n", ans);
}