inversion(求逆序数，逆序数求序列，用线段树).cpp

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

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

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

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

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

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

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);
	}
}

void
cal_P()
{
	int i,j;
	for(i=1;i<=n;i++) {
		anti = 0;
		update(root, num[i]);
		ans[ num[i] ] = anti;
	}
}

void
cal_I()
{
	int i,j;
	for(i=1;i<=n;i++) {
		ans[ find(root, num[i]) ] = i;
	}
}

int
main()
{
	int i,j;
	while(scanf("%d", &n)==1) {
		if(n==0) {
			break;
		}
		getchar();
		char cmd = getchar();
		mem_pos = 0;
		for(i=1;i<=n;i++) {
			scanf("%d", &num[i]);
			ans[i] = 0;
		}
		if(cmd == 'P') {
			root = make_tree(1, n, false);
			cal_P();
		}
		else {
			root = make_tree(1, n, true);
			cal_I();
		}
		for(i=1;i<n;i++) {
			printf("%d ", ans[i]);
		}
		printf("%d\n", ans[n]);
	}
}