CF501D Misha and Permutations Summation(康托展开)

#pragma warning(disable:4996)
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

#define maxn 210000

int bit[maxn];
int n;

void upd(int i)
{
	while (i <= n){
		bit[i] += 1;
		i += i&(-i);
	}
}

void dec(int i)
{
	while (i <= n){
		bit[i] -= 1;
		i += i&(-i);
	}
}

int cal(int i)
{
	int ret = 0;
	while (i > 0){
		ret += bit[i];
		i -= i&(-i);
	}
	return ret;
}

int solve(int x)
{
	int l = 1, r = n+1;
	while (l < r)
	{
		int mid = (l + r) >> 1;
		int tx = cal(mid);
		if (tx < x) l = mid + 1;
		else r = mid;
	}
	return l;
}

int a[maxn];
int b[maxn];
int c[maxn];
int va[maxn];
int vb[maxn];
int vc[maxn];

int main()
{
	while (cin >> n)
	{
		for (int i = 0; i < n; ++i){
			scanf("%d", a + i); a[i]++;
		}
		for (int i = 0; i < n; ++i){
			scanf("%d", b + i); b[i]++;
		}
		memset(bit, 0, sizeof(bit));
		for (int i = n - 1; i >= 0; --i){
			va[i] = cal(a[i]);
			upd(a[i]);
		}
		memset(bit, 0, sizeof(bit));
		for (int i = n - 1; i >= 0; --i){
			vb[i] = cal(b[i]);
			upd(b[i]);
		}
		reverse(va, va + n);
		reverse(vb, vb + n);
		memset(vc, 0, sizeof(vc));
		int carry = 0;
		for (int i = 1; i < n; ++i){
			vc[i] = (carry + va[i] + vb[i]) % (i + 1);
			carry = (carry + va[i] + vb[i]) / (i + 1);
		}
		reverse(vc, vc + n);
		memset(bit, 0, sizeof(bit));
		for (int i = 1; i <= n; ++i){
			upd(i);
		}
		for (int i = 0; i < n; ++i){
			c[i] = solve(vc[i]+1);
			dec(c[i]);
		}
		for (int i = 0; i < n; ++i){
			if (i) printf(" ");
			printf("%d", c[i]-1);
		}
		puts("");
	}
	return 0;
}