HDU - 4911 Inversion

3 1
2 2 1
3 0
2 2 1

1
2

題意：求經過最多k次相鄰的交換的操作，使得序列的逆序數對最小是多少

思路：線段樹和樹狀數組錯了，然後就用歸並排序的方法得到當前序列的逆序數對，然後就是想如果想得到最小的話，那麼我們每次能的是把大的數放到後面，這樣逆序數會減一，然後就能得到答案了

#include 
#include 
#include 
#include 
typedef long long ll;
using namespace std;
const int maxn = 1e5 + 10;

int a[maxn], b[maxn<<1];
int n, k;
ll ans;

void msort(int s, int t) {
	int mid = (s + t) >> 1;
	int qb = 1, bn = t-s+1;
	if (s >= t)
		return;
	msort(s, mid);
	msort(mid+1, t);
	int i, j;
	for (i = s, j = mid+1; i <= mid && j <= t; ) {
		if (a[i] <= a[j]) {
			b[qb] = a[i];
			i++;
		}
		else {
			b[qb] = a[j];
			ans += mid-i+1;
			j++;
		}
		qb++;
	}
	while (i <= mid) 
		b[qb++] = a[i++];
	while (j <= t)
		b[qb++] = a[j++];
	for (i = 1, j = s; i < qb; i++, j++)
		a[j] = b[i];
}

int main() {
	while (scanf("%d%d", &n, &k) != EOF) {
		ans = 0;
		for (int i = 1; i <= n; i++)
			scanf("%d", &a[i]);
		msort(1, n);
		cout << max((ll)0, ans-k) << endl;
	}	
	return 0;
}