题目大意

给定一个长度为 $N$ 的序列 $d_i$。

你有一个长度为 $N$ 的序列 $a_i$，初始状态下 $a_i=i$。

你需要每次交换序列 $a_i$ 中相邻的两个数，使得最终满足对于任意的 $1\le i\le n$，均有 $a_i\le d_i$。求出最少需要多少次。

分析

假设我们已经构造出了序列 $a$，那么最小的交换次数就是序列 $a$ 中逆序对的数量。

所以，问题就转化成了：构造一个 $1$ 到 $n$ 的排列 $a$，使得 $a_i\le d_i$，且 $a$ 中逆序对的数量尽可能少。

可以发现，我们需要让排在后面的数尽可能的大，才能使得逆序对的数量尽可能少。

这里用了一个树状数组维护当前已经填充过的数，并用一个二分来对当前最大的满足限制的数进行查找。

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int n;
int a[200005], pre[200005];
int c[200005];
ll tot;
void add(int x) {
	for(; x <= n ;  x += x & -x) c[x]++; 
}
int ask(int x) {
	if(x == 0) return 0;
	int ans = 0;
	for(; x ; x -= x & -x) ans += c[x];
	return ans; 
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for(int i = n; i >= 1; i--) {
		int l = 1, r = a[i], mid, ans = -1, sum = ask(a[i]);
		while(l <= r) {
			mid = l + r >> 1;
			if(sum - ask(mid - 1) < a[i] - mid + 1) l = mid + 1, ans = mid;
			else r = mid - 1;
		}
		if(ans == -1) {
			puts("-1");
			return 0;
		}
		tot += ask(ans);
		add(ans);
	}
	printf("%lld", tot);
	return 0;
}