3
$\begingroup$

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],[1,2,3,4,5]$ and $[4,3,1,2]$. The following arrays are not permutations: $[2],[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.

$\endgroup$
3
  • $\begingroup$ @Mike You are right that in a standard segment tree, updating an interval of leaves requires $O(n)$ time: Actually this is already somewhat of an improvement over the naive approach where you call update on each leaf; since a single update takes $O(\log n)$ time (the single leaf change propagates up to the root), then updating all leaves[k] for $i\leq k \leq j$ could take $O(n\log n)$ time. To get to $O(n)$ time, what you are doing is updating all the leaves in sequence, then recomputing the tree from the leaves to the root, and since there are $2N$ nodes, this is $O(n)$ time. $\endgroup$
    – Matthew C
    Oct 31, 2019 at 18:07
  • $\begingroup$ All that is to say, that you can augment your standard segment tree so that the following particular kind of interval update takes $O(\log N)$ time: increment all leaves $k$ in $i\leq k \leq j$ by the same constant $C$. Note this isn't the same as the above discussion, where you could update leaves to their unique new values in total $O(N)$ time; here you really must be calling the same kind of update on all leaves in your interval. Anyway, for instructions on how to augment your segment tree see geeksforgeeks.org/lazy-propagation-in-segment-tree $\endgroup$
    – Matthew C
    Oct 31, 2019 at 18:09
  • $\begingroup$ And you can see in your problem that this is exactly the kind of update you are doing; decrementing ALL leaves to the right of some given node by a constant; "all leaves to the right" is an interval of leaves, and the decrement is by the same amount for each ($-i$, at step $i$ in the solution)) $\endgroup$
    – Matthew C
    Oct 31, 2019 at 18:13

1 Answer 1

-1
$\begingroup$

The segment tree is useful in this problem because you need to maintain an array of values where the supported operations are: 1) decrementing all elements in a range by the same amount and 2) querying a range for its (rightmost) minimum-value location.

In this problem, the values maintained in the array are the sums $s_i$, that have to be adjusted as described by the solution.

In your example, the subsequent contents of the array will be as follows:

0 1 1 1 10 # we query range (1, 5) and obtain position 1 (rightmost minimum)
∞ 1 1 1 10 # we remove the value at position 1, by setting it to INFINITY
∞ 0 0 0 9  # we subtract 1 from all values to its right (range (2, 5))
∞ 0 0 0 9  # we query range (1, 5) and obtain position 4 (rightmost minimum)
∞ 0 0 ∞ 9  # we remove the value at position 4
∞ 0 0 ∞ 7  # we subtract 2 from all values to its right (range (5, 5))
∞ 0 0 ∞ 7  # we query range (1, 5) and obtain position 3 (rightmost minimum)
∞ 0 ∞ ∞ 7  # we remove the value at position 3
∞ 0 ∞ ∞ 4  # we subtract 3 from all values to its right
∞ 0 ∞ ∞ 4  # we query range (1, 5) and obtain position 2 (rightmost minimum)
∞ ∞ ∞ ∞ 4  # we remove the value at position 2
∞ ∞ ∞ ∞ 0  # we subtract 4 from all values to its right
∞ ∞ ∞ ∞ 0  # we query range (1, 5) and obtain position 5 (rightmost minimum)
∞ ∞ ∞ ∞ ∞  # we remove the value at position 5 and stop. 

Since the sequence of minimum positions was P = [1, 4, 3, 2, 5], it means that in the hidden permutation number 1 is at position 1, number 2 is at position 4, and so on. Hence the hidden permutation is [1, 4, 3, 2, 5], the inverse of P (although in this case it's the same).

$\endgroup$
1
  • $\begingroup$ I think this treads ground that's already familiar to OP. What they need to know is why "update range" can be done in $O(\log n)$ time (and the answer to that is lazy propagation). $\endgroup$
    – Matthew C
    Dec 1, 2019 at 22:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.