factorial number system and finding lex permutation

Pemutation to factoradic conversions:
Given a permuation 3,0,2,1. It's factoradic representation is not simply 4132!. We have to put some mind to it.

We have n=4. So we have A×3!+B×2!+C×1!+D×0!. We have to find the values of A,B,C and D.

A = We can simply do that by finding number of elements smaller than 3. That is 3.
Now we remove 3 from consideration, and have {0,1,2}.
B = Number of elements smaller than 0? None. So 0. Remove 0. We're left with {1,2}.
C = Number of elements smaller than 2? 1. So 1. We have {1} left.
D = 0
So, we have 3010!, representing 3,0,2,1. To double check, you can find the decimal value, which comes out to be: 3×3!+0×2!+1×1!+0×0!=18+0+1+0=19

As you can see here, 3021, is indeed the 19th permutation for n=4.

The basic inference you can get from here is that factoradic representation gives the rank of the number, for the remaining numbers.

This can be done by fenwick trees / Binary indexed trees, easily


 problem : https://codeforces.com/contest/501/problem/D