## 504B

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

### Description

Give you two permutations of $n$ integers of $0$ to $n - 1$. ($1 \leq n \leq 2\times 10^5$). Posit they are the $a$th and $b$th permutation. Output the $(a + b) \% n$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. $rank = \sum\limits_{i=1}^{n}{less(p_i) \times (n - i)!}$. $p_i$ is the $i$th number in the permutation. $less(p_i)$ means the number of $p_j$ which is less than $p_i$ and $j$ is greater than $i$, which can be calculated by binary indexed tree. With this formula we can calculate $a+b$ like we add two big integers. $less(p_i)$s are the digits of the big integers. We need to do the carry bit.</p>

After that we have the $a+b$ and we need to transform it back to the $a + b$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]);
}
}

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++)
for (int i = 1; i <= n; i++)
{
c[i] = binary_search(1, n, sum_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;
}