Inversions 2

Array of inversions a is given. You need to restore the permutation p. Let's build a segment tree of size n, which is filled with ones, and is able to respond to the request k-th one from the end. (finding the k-th one from the end is similar to the task of finding the k-th one from the beginning from step 2) Now, let's process the elements from right to left. A one in a leaf of a segment tree will mean that an element with this value is to the left. When moving to the i-th element, we will look for the a[i]-th one from the right: this just means that there will a[i] greater elements to the left of the i-th position. Finally, put 0 in the found position, i.e. remove the element from consideration. The total time is O(nlogn).

You went over this in step 2.

The solution uses a segment tree for the k-th one.

Inversions 2

Array of inversions a is given. You need to restore the permutation p. Let's build a segment tree of size n, which is filled with ones, and is able to respond to the request k-th one from the end. (finding the k-th one from the end is similar to the task of finding the k-th one from the beginning from step 2) Now, let's process the elements from right to left. A one in a leaf of a segment tree will mean that an element with this value is to the left. When moving to the i-th element, we will look for the a[i]-th one from the right: this just means that there will a[i] greater elements to the left of the i-th position. Finally, put 0 in the found position, i.e. remove the element from consideration. The total time is O(nlogn).