Codeforces Round 285 (Div. 2 D or Div. 1 B) - Misha and Permutations Summation

Problem Statement:
504B - Misha and Permutations Summation

Solution:
Another nice problem. Firstly we need to exactly understand how to compute the "position" of a certain lexicographical permutation, where the convention is that P(0) = [0,1,2,3,...,n-1] while P(n!-1) = [n-1,n-2,...,0].

Let's consider the following example:

pos: 0 1 2 3 4 5 6
a  : 4 5 3 6 1 2 0

Now, we know that for '4' to reach '0' position, first from [0,1,2,3,4,5,6], it has to go to [1,0,2,3,4,5,6], then to [2,0,1,3,4,5,6], then to [3,0,1,2,4,5,6] and finally [4,0,1,2,3,5,6]. In reach each subsequent permutation state, each of them needs to go through 6! lexicographical permutations, so in total we need 4 * 6! to move 4 from its original position in P(0) to position 0. We iteratively compute on subsequent elements, in exactly the same way using the same reasoning. However, since each iteration removes one number from the next subsequent consideration, we need an efficient way to check what numbers have been removed. Here segment tree plays the hero again! Without segment tree, in total we will have \(O(N^2)\), but implementation using segment tree will push it down to \(O(N\lg{N})\).



Once the "position" of each permutation a and b has been found, we can add them up with \(k!\) used as the basis, and since we need to mod the result with \(n!\), we can come up with the final position in \(O(N)\) time. From this final position, finding the final sequence is a matter of reverse engineering the above process for finding the position initially.

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

int st[800003];
int a[200003], b[200003];
int p[200003], q[200003];
int N;

void reset_st(int p=1, int L=0, int R=N-1){
    if(L==R){
        st[p] = 1;
        return;
    }
    int M = (L+R)/2;
    reset_st(2*p,L,M);
    reset_st(2*p+1,M+1,R);
    st[p] = st[2*p]+st[2*p+1];
}

void delete_elem(int S,int p=1,int L=0,int R=N-1){
    if(R<S || S<L)return;
    if(L==R && R==S){
        st[p] = 0;
        return;
    }
    int M=(L+R)/2;
    delete_elem(S,2*p,L,M);
    delete_elem(S,2*p+1,M+1,R);
    st[p] = st[2*p]+st[2*p+1];
}

int rmq(int S,int T,int p=1,int L=0,int R=N-1){
    if(R<S||T<L)return -1;
    if(S<=L && R<=T)return st[p];
    int M=(L+R)/2;
    int left = rmq(S,T,2*p,L,M);
    int right = rmq(S,T,2*p+1,M+1,R);
    if(left == -1)return right;
    if(right == -1)return left;
    return left+right;
}

int find(int pos,int p=1,int L=0,int R=N-1){
    if(L==R){
        return L;
    }
    int M=(L+R)/2;
    int left = rmq(L,M,2*p,L,M);
    if(pos-left > 0){
        return find(pos-left,2*p+1,M+1,R);
    } else {
        return find(pos,2*p,L,M);
    }
}

int main(){
    scanf("%d",&N);
    for(int i=0;i<N;++i){
        scanf("%d",&a[i]);
    }
    for(int i=0;i<N;++i){
        scanf("%d",&b[i]);
    }
    reset_st();
    for(int i=0;i<N;++i){
        p[i] = rmq(0,a[i])-1;
        delete_elem(a[i]);
    }
    reset_st();
    for(int i=0;i<N;++i){
        q[i] = rmq(0,b[i])-1;
        delete_elem(b[i]);
    }
    for(int i=0;i<N;++i){
        p[i] += q[i];
    }
    for(int i=N-1;i>=0;--i){
        int k = N-i-1;
        if(p[i]>k){
            if(i!=0)p[i-1]++;
            p[i] -= k+1;
        }
    }
    reset_st();
    for(int i=0;i<N;++i){
        if(i!=0)printf(" ");
        int k = find(p[i]+1);
        printf("%d", k);
        delete_elem(k);
    }
    printf("\n");
    return 0;
}