504B

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.

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]);
        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;
}