Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)

Codeforces Round #285 (Div. 1)B. Misha and Permutations Summation（数学+数据结构打脸)

Let's define the sum of two permutations p and q of numbers 0, 1, ..., (n - 1) as permutation $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$ , where Perm(x) is the x-th lexicographically permutation of numbers 0, 1, ..., (n - 1) (counting from zero), and Ord(p) is the number of permutation p in the lexicographical order.

For example, Perm(0) = (0, 1, ..., n - 2, n - 1), Perm(n! - 1) = (n - 1, n - 2, ..., 1, 0)

Misha has two permutations, p and q. Your task is to find their sum.

Permutation a = (a0, a1, ..., an - 1) is called to be lexicographically smaller than permutation b = (b0, b1, ..., bn - 1), if for some k following conditions hold: a0 = b0, a1 = b1, ..., ak - 1 = bk - 1, ak < bk.

Input

The first line contains an integer n (1 ≤ n ≤ 200 000).

The second line contains n distinct integers from 0 to n - 1, separated by a space, forming permutation p.

The third line contains n distinct integers from 0 to n - 1, separated by spaces, forming permutation q.

Output

Print n distinct integers from 0 to n - 1, forming the sum of the given permutations. Separate the numbers by spaces.

Sample test(s)

input
2
0 1
0 1

output
0 1

input
2
0 1
1 0

output
1 0

input
3
1 2 0
2 1 0

output
1 0 2

Note

Permutations of numbers from 0 to 1 in the lexicographical order: (0, 1), (1, 0).

In the first sample Ord(p) = 0 and Ord(q) = 0, so the answer is $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$ .

In the second sample Ord(p) = 0 and Ord(q) = 1, so the answer is $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$ .

Permutations of numbers from 0 to 2 in the lexicographical order: (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), (2, 1, 0).

In the third sample Ord(p) = 3 and Ord(q) = 5, so the answer is $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$ .

引用官方题解：

504B - Misha and Permutations Summation

To solve the problem, one need to be able to find the index of given permutation in lexicographical order and permutation by its index. We will store indices in factorial number system. Thus number x is represented as $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$ . You can find the rules of the transformhere.

To make the transform, you may need to use data structures such as binary search tree or binary indexed tree (for maintaining queries of finding k-th number in the set and finding the amount of numbers less than given one).

So, one need to get indices of the permutations, to sum them modulo n! and make inverse transform. You can read any accepted solution for better understanding.

Time complexity: $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$ or $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$ .

本题需要会用阶乘来表示一个数字，并能用这种方式来在数与排列之间进行映射（具体见维基http://en.wikipedia.org/wiki/Factorial_number_system)，需要快速查询名次和求第k大。用bit可以在 $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$ .完成bbst只需要需要 $Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)$

#include <bits/stdc++.h>
#define foreach(it,v) for(__typeof(v.begin()) it = v.begin(); it != v.end(); ++it)
const int maxn = 2e5 + 10;
using namespace std;
typedef long long ll;
int a[maxn],b[maxn],c[maxn],p[maxn],n;
int pa[maxn],pb[maxn];
void Modify(int x,int val)
{
	while(x <= n) {
		c[x] += val;
		x += x & -x;
	}
}
int Query(int k,int limt = 20)
{
	int ans = 0,cnt = 0;
	for(int i = limt; i >= 0; i--) {
		ans += (1<<i);
		if(ans > n||cnt + c[ans]>=k) ans -= (1<<i);
		else cnt += c[ans];
	}
	return ans + 1;
}
int work(int x,int R)
{
	int L = 1;
	while(L < R) {
		int mid = (L + R) >> 1;
		int t = Query(mid);
		if(x == t)return mid;
		if(x > t) L = mid;
		else R = mid;
	}
	return L - 1;
}
int main(int argc, char const *argv[])
{
	ios_base::sync_with_stdio(false);
	while(cin>>n) {
		memset(c,0,sizeof (c[0])*(n+1));
		for(int i = 0; i < n; i++) {
			cin>>a[i];
			++a[i];
			Modify(a[i],1);
		}
		int R = n;
		for(int i = 0; i < n; i++) {
			pa[i] = work(a[i], R + 1) - 1;
			R--;
			Modify(a[i],-1);
		}
		memset(c,0,sizeof (c[0])*(n+1));
		for(int i = 0; i < n; i++) {
			cin>>b[i];
			++b[i];
			Modify(b[i],1);
		}
		R = n;
		for(int i = 0; i < n; i++) {
			pb[i] = work(b[i], R + 1) - 1;
			R--;
			Modify(b[i],-1);
		}
		memset(p,0,sizeof(p[0])*(n+1));
		for(int i = n-1; i >= 0; i--) {
			p[i] += pa[i] + pb[i];
			if(i)p[i-1] = p[i] / (n-i);
			p[i] %= (n-i);
		}
		// for(int i = 0; i < n; i++)printf("%d%c", pa[i]," \n"[i+1==n]);
		// for(int i = 0; i < n; i++)printf("%d%c", pb[i]," \n"[i+1==n]);
		// for(int i = 0; i < n; i++)printf("%d%c", p[i]," \n"[i+1==n]);
		memset(c,0,sizeof (c[0])*(n+1));
		for(int i = 0; i < n; i++) {
			Modify(i+1,1);
		}
		for(int i = 0; i < n; i++) {
			int t = Query(p[i]+1);
			printf("%d%c", t-1," \n"[i+1==n]);
			Modify(t,-1);
		}
	}
	return 0;
}

Codeforces Round #285 (Div. 一)B. Misha and Permutations Summation（数学+数据结构打脸)

相关推荐