inversion(构造逆序数用线段树).cpp

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

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

struct node {
	long long l,r;
	node * pl, * pr;
	long long count;
}mem[150000];
long long mem_pos;
long long anti, n, ans[51000];

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

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

long long
find(node * root, long long 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);
	}
}

long long
get_max(long long x, long long y)
{
	return x > y ? x : y;
}

int
main()
{
	long long i,j;
	while(scanf("%lld %lld", &n,&anti)==2) {
		if(n==-1 && anti==-1) {
			break;
		}
		for(i=1;i<=n;i++) {
			long long t = (n-i)*(n-i-1)/2;
			ans[i] = get_max(0, anti - t);
			anti -= ans[i];
		}
		mem_pos = 0;
		node * root = make_tree(1, n);
		for(i=1;i<n;i++) {
			printf("%lld ", find(root, ans[i]+1));
		}
		printf("%lld\n", find(root, ans[n]+1));
	}
}