Indian Computing Olympiad

Training Material


Range Queries→From inversions to permutations

Given a permutation that maps each i to P(i), Inversion(i) is the number of j < i that appear to the right of i in the permutation. We can thus associate with each permutation, an inversion sequence. An example is given below.

                     1  2  3  4  5  6  7  8
Permutation P(i)     2  3  1  6  7  8  4  5
Inversion   I(i)     0  1  1  0  0  2  2  2
      

How do we recover the permutation from the inversion sequence?

Solution