[knuthsat]

Decoding the k-th permutation:

1: 1 2 3 4 5

2: 1 2 3 5 4

3: 1 2 4 3 5

Number 3 codes into operations that manipulate 1 2 3 4 5 sequence ( https://en.wikipedia.org/wiki/Factorial_number_system ):

1. get 0th elem twice (1 2) 2. get 1st elem (4) 3. get 0th elem twice (3 5)

The data you are maintaining in the segment tree allows you to get the elements out of 1 2 3 4 5 sequence in O(log n), and when you remove the element O(log n), the structure can tell you again what the k-th element is.

If you hold the data in a normal array, you get quadratic algorithm.

Of course, you can use a different tree that allows you to get the k-th element of a sorted sequence but segment trees are easy to code in comppro setting.