504B


  Posted on 16 Jan 2015
combinatorial mathematics data structures binary indexed tree

Description


Give you two permutations of integers of to . (). Posit they are the th and th permutation. Output the th permutation.

Tutorial


With the thought of dynamic programming, we can come up with the formula of calculating the rank of a permutation, which is as follows. . is the th number in the permutation. means the number of which is less than and is greater than , which can be calculated by binary indexed tree. With this formula we can calculate like we add two big integers. s are the digits of the big integers. We need to do the carry bit.</p>

After that we have the and we need to transform it back to the th permutation, which can be done by binary indexed tree and binary search.


Solution


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

#define D(x) 

const int MAX_N = (int)(1e5) * 2 + 10;

int n;
int a[MAX_N];
int b[MAX_N];
int sum_b[MAX_N];
int sum_a[MAX_N];
int c[MAX_N];
int sum_c[MAX_N];

int binary_indexed_tree[MAX_N];

int low_bit(int x)
{
	return x & (-x);
}

void add(int pos, int val)
{
	for (int i = pos; i < MAX_N; i += low_bit(i))
	{
		binary_indexed_tree[i] += val;
	}
}

int sum(int pos)
{
	int ret = 0;
	for (int i = pos; i > 0; i -= low_bit(i))
	{
		ret += binary_indexed_tree[i];
	}
	return ret;
}

void input(int a[])
{
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		a[i]++;
	}
}

void work(int sum_a[], int a[])
{
	fill(binary_indexed_tree, binary_indexed_tree + n + 1, 0);
	for (int i = n; i; i--)
	{
		sum_a[i] = sum(a[i]);
		add(a[i], 1);
	}
}

bool ok(int mid, int a)
{
	return sum(mid) >= a;
}

int binary_search(int start, int end, int a)
{
	int l = start;
	int r = end;
	while (l < r)
	{
		int mid = (l + r) / 2;
		if (ok(mid, a))
			r = mid;
		else
			l = mid + 1;
	}
	return l;
}

int main()
{
	//input
	scanf("%d", &n);
	input(a);
	input(b);

	//work
	work(sum_a, a);
	work(sum_b, b);
	for (int i = 1; i <= n; i++)
	{
		sum_c[i] = sum_a[i] + sum_b[i];
	}
	for (int i = n; i; i--)
	{
		if (sum_c[i] > n - i)
		{
			sum_c[i] -= n - i + 1;
			sum_c[i - 1] += 1;
		}
	}
	fill(binary_indexed_tree, binary_indexed_tree + n + 1, 0);
	for (int i = 1; i <= n; i++)
		add(i, 1);
	for (int i = 1; i <= n; i++)
	{
		c[i] = binary_search(1, n, sum_c[i] + 1);
		add(c[i], -1);
	}
	D(for (int i = 1; i <4; i++) printf("%d\n", sum_c[i]));

	//output
	for (int i = 1; i <= n; i++)
	{
		printf("%d", c[i] - 1);
		if (i != n)
			putchar(' ');
	}
	puts("");
	return 0;
}