自动搬运

查看原文

来自洛谷，原作者为

	Betrayer_of_love QQ：1764517061||念念不忘，必有回响||互关私

搬运于2025-08-24 22:22:41，当前版本为作者最后更新于2025-04-06 19:58:05，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

解析：

考虑依次填入每个位置。 最后一个位置只能填 $d_i=n$ 的位置，第 $k$ 个位置只能填 $d_i \ge k$ 。

我们随着 $k$ 的减小，决策集合扩大。

那么对于第 $n$ 个位置，一定选择 $d_i=n$ 中最大的 $i$ 。依次类推，第 $k$ 个位置肯定选择决策集合中最大的数。

需要在线维护加入一个数，查询最大值和删除最大值，直接用优先队列即可。

最后再用树状数组求出逆序对。

代码：

#include<bits/stdc++.h>
#define int long long 
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 200005
using namespace std;
int n, d[N], c[N];
vector<int>u[N];
inline void add(int x) {
	for (; x <= n; x += x & -x)c[x]++;
}
inline int ask(int x) {
	int sum = 0;
	for (; x; x -= x & -x)sum += c[x];
	return sum;
}
priority_queue<int>q;
signed main() {
	scanf("%d", &n);
	int ans = 0;
	rep(i, 1, n)scanf("%d", &d[i]), u[d[i]].push_back(i);
	pre(i, n, 1) {
		for (int j = 0; j < (int)u[i].size(); j++)q.push(u[i][j]);
		if (q.empty()) {
			puts("-1");
			return 0;
		}
		int cur = q.top();
		q.pop();
		ans += ask(cur);
		add(cur);
	}
	printf("%lld\n", ans);
	return 0;
}

完结撒花，谢谢