提交记录

以下是我用cdq分治写出来的40分代码

球球了QwQ

#include<bits/stdc++.h>
using namespace std;
int n;
typedef long long ll;
const int maxn = 1e5 + 5;
int c[maxn], a[maxn], b[maxn];
ll ans;
#define half (l + r) >> 1
void cdq(int l, int r) {
	if(!(l ^ r)) return;
	int mid = half;
	cdq(l, mid);
	cdq(mid + 1, r);
	int ql = l, qr = mid + 1, pos = l;
	while(ql <= mid || qr <= r) {
		if(ql > mid) {
			b[pos ++] = a[qr ++];
			ans += ql - l;
		}
		else if(qr > r) {
			b[pos ++] = a[ql ++];
		}
		else {
			if(a[ql] > a[qr]) {
				b[pos ++] = a[ql ++];
			}
			else {
				b[pos ++] = a[qr ++];
				ans += ql - l;
			}
		}
	}
	for(int i = l; i <= r; i ++) a[i] = b[i];
}
int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i ++) {
		scanf("%d", &i[c]);
		a[i] = c[i];
	}
	cdq(1, n);
	ll tmp = ans;
	for(int i = 1; i < n; i ++) {
		tmp = tmp - ((ll)c[i] - 1) + ((ll)n - c[i]);
		ans = min(ans, tmp);
	}
	printf("%lld\n", ans);
	return 0;
}