I encountered the following problem on Codeforces.
An array of integers $p_1,p_2,…,p_n$ is called a permutation if it contains each number from 1 to n exactly once. For example, the following arrays are permutations: $[3,1,2],,[1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $,[1,1],[2,3,4]$.
There is a hidden permutation of length $n$.
For each index $i$, you are given $s_i$, which equals to the sum of all $p_j$ such that $j<i$ and $p_j<p_i$. In other words, $s_i$ is the sum of elements before the $i$-th element that are smaller than the $i$-th element.
Your task is to restore the permutation.
How can I solve this problem using segment trees in $O(n\log n)$ time?
I tried to understand the solution on Codeforces but I could not understand it. Their solution:
Let us fill the array with numbers from 1 to $N$ in increasing order.
1 will lie at the last index $i$ such that $s_i=0$. Find and remove this index $i$ from the array and for all indices greater than $i$, reduce their $s_i$ values by $1$. Repeat this process for numbers $2,3,\ldots,N$. In the $i$th turn, reduce the elements by $i$.
To find the last index with value zero, we can use segment tree to get range minimum query with lazy propagation.
I do not understand what is stored in segment tree (like least number in the given range) and how the update is done in $O(\log n)$ time in this case. Can you show me an example input and show me what happens in each iteration?
My attempt: I tried to solve this problem by making a segment tree where each node will contain the smallest number in the range corresponding to that node. But I was not able to solve the problem.
For example: Suppose I have sample input:
5 0 1 1 1 10
My segment tree will look like:
[1-5](0) / \ [1-2](0) [3-5](1) / \ / \ [1-1](1) [2-2](1) [3-4](1) [5-5](10) / \ [3-3](1) [4-4](1)
Value adjacent to each range is minimum value in its sub tree. I failed to solve using this approach since update will take $O(n)$ time.