yesterday I had a coding interview in which I was asked the following problem which I was not able to solve. please help me to figure out an approach for this problem.

Problem: Alex has a permutation of first n natural numbers in an array A for this permutation he has calculated another array B which is done as follows

B[i] will contain the number of elements on left of index i which are bigger then a[i], now somehow Array A is lost then we have to regenerate the array A from array B.

This problem is quite similar to https://codeforces.com/contest/1208/problem/D

You can initialise all elements of a Fenwick tree to 1 and binary search for the value while traversing array B from right to left and updating the found value to 0.

Thank you.

You can determine the last element as n — b[n]. Now proceed from the back and keep a track of the used up elements and the available elements and check if placing a given value satisifies the constraint. Naively I think it can be done in O(n ^ 2) and then optimise using sets.

The assertion I think would be that the permutation is unique as at any stage our invariant is that there is a finite list and only placing a particular element would satisfy the constraint. The invariant holds vacuously at the end(pos = n) and hence it will hold at termination as well

oh i was close to this but I got distracted from this approach.

You can use a segment tree to mark the visited elements as 0(set all indices of segment tree to 1 initially) and then query for sum range in segment tree whose value is b[i] while traversing b from back.

Sorry for my English.

thanks for sharing.

You can solve it from the rightmost element using fenwick/segment tree + binary search in

`O(n log^2(n))`

.Another alternatives is to use pbds or bbst and then solve them in

`O(n log(n))`

.