minimum inversion number(线段树求逆序数).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;

struct node {
	int l,r;
	node * pl, * pr;
	int count;
}mem[13000];
int mem_pos;
int n,num[5100];
int anti, ans;

node *
new_node()
{
	node * pt = &mem[mem_pos ++];
	memset(pt,0,sizeof(node));
	return pt;
}

node *
make_tree(int il, int ir)
{
	node * root = new_node();
	root ->l = il;
	root ->r = ir;
	if(il != ir) {
		int mid = (il+ir)/2;
		root ->pl = make_tree(il, mid);
		root ->pr = make_tree(mid+1, ir);
	}
	return root;
}

void
update(node * root, int num)
{
	root ->count ++;
	if(root ->l == num && root ->r == num) {
		return ;
	}
	if(root ->pl ->r >= num) {//left
		anti += root ->pr ->count;
		update(root ->pl, num);
	}
	else {//right
		update(root ->pr, num);
	}
}

int main()
{
	int i,j;
	while(scanf("%d", &n)==1) {
		anti = 0;
		mem_pos = 0;
		node * root = make_tree(0,n-1);
		for(i=0;i<n;i++) {
			scanf("%d", num+i);
			update(root, num[i]);
		}
		ans = anti;
		for(i=0;i<n;i++) {
			anti += n-1 -2*num[i];
			ans = min(ans, anti);
		}
		printf("%d\n",ans);
	}
}