Overview

This problem asks us to reconstruct the original permutation \(P\) given information about the number of elements before each element that are greater than itself. By determining the positions of people in increasing order of height, the problem reduces to “finding the \(k\)-th empty slot from the front,” which can be solved efficiently in \(O(N \log N)\) time using a Binary Indexed Tree (BIT).

Analysis

1. Determining from Smallest to Largest Values

The key to this problem is to determine the positions in increasing order of height (\(x = 1, 2, \dots, N\)).

When determining the position of the person with height \(x\), assume that the positions of smaller values \(1, 2, \dots, x - 1\) have already been determined. At this point, any “empty slot” where no person has been placed yet will eventually be occupied by one of \(x, x+1, \dots, N\). In other words, any currently empty slot will definitely be occupied by someone with height \(x\) or greater.

The fact that there are \(A_x\) people taller than \(x\) standing before the person with height \(x\) means that the person with height \(x\) must be placed in the \((A_x + 1)\)-th empty slot from the front among the currently unoccupied slots.

Concrete Example (for \(N = 4, A = (1, 2, 0, 0)\))

Initially, all slots \(1, 2, 3, 4\) are empty. 1. Placing \(x = 1\): - Since \(A_1 = 1\), \(1\) is placed in the \((1 + 1 = 2)\)-nd empty slot from the front (slot \(2\)). - Remaining empty slots: \([1, 3, 4]\) 2. Placing \(x = 2\): - Since \(A_2 = 2\), \(2\) is placed in the \((2 + 1 = 3)\)-rd empty slot from the front (slot \(4\)). - Remaining empty slots: \([1, 3]\) 3. Placing \(x = 3\): - Since \(A_3 = 0\), \(3\) is placed in the \((0 + 1 = 1)\)-st empty slot from the front (slot \(1\)). - Remaining empty slots: \([3]\) 4. Placing \(x = 4\): - Since \(A_4 = 0\), \(4\) is placed in the \((0 + 1 = 1)\)-st empty slot from the front (slot \(3\)).

As a result, the permutation \(P = (3, 1, 4, 2)\) is reconstructed.

2. Naive Approach and Its Limitations

If we maintain the empty slots using an array or list and directly perform the operation “retrieve and remove the \(k\)-th element from the front,” each removal takes \(O(N)\) time. Repeating this \(N\) times leads to an overall time complexity of \(O(N^2)\), which will exceed the time limit (TLE) under the constraint \(N \le 2 \times 10^5\).

3. Speeding Up with Data Structures

Consider an array where each slot is \(1\) if it is empty and \(0\) if it is occupied. Then, “the \(k\)-th empty slot from the front” can be rephrased as the smallest index whose prefix sum is exactly \(k\). Data structures such as a Binary Indexed Tree (BIT) or a Segment Tree allow us to efficiently update values (\(1 \to 0\)) and query prefix sums. Furthermore, by performing binary search directly over the tree structure of the BIT (binary search on BIT / binary lifting), each query can be processed in \(O(\log N)\) time.

Algorithm

1. Initialize the BIT:
   • Prepare an array of length \(N\), initializing all elements to \(1\) (empty slot).
   • Construct the BIT in \(O(N)\) time instead of performing repeated point updates.
2. For each \(x = 1, 2, \dots, N\), do the following:
   • Let target be the desired empty slot number: \(A_x + 1\).
   • Using binary search on the BIT, find the index pos whose prefix sum equals target in \(O(\log N)\) time.
   • Assign \(x\) to position pos in the answer array.
   • Since slot pos is now filled, subtract \(1\) from the value at pos in the BIT (so it is no longer counted as an empty slot).
3. Output the reconstructed array.

Complexity

• Time Complexity: \(O(N \log N)\)
  • Initializing the BIT takes \(O(N)\) time.
  • For each step from \(x = 1\) to \(N\), binary search on the BIT takes \(O(\log N)\), and updating the value takes \(O(\log N)\), resulting in \(O(N \log N)\) for the entire loop.
  • This runs well within the time limit for \(N = 2 \times 10^5\).
• Space Complexity: \(O(N)\)
  • \(O(N)\) memory is used for the BIT and the array storing the permutation.

Implementation Details

• Binary Search on BIT (Binary Lifting): A naive binary search (e.g., calling the BIT’s query inside bisect) takes \(O(\log^2 N)\) time. However, by determining the index bit by bit from the most significant bit along the BIT tree structure, the target index can be found in \(O(\log N)\) time.

• Index Mapping: A BIT is typically implemented as 1-indexed. Pay close attention to index conversions between the BIT and the output array (which is usually 0-indexed).

  Source Code

import sys


def solve():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    N = int(input_data[0])
    A = [int(x) for x in input_data[1 : N + 1]]

    bit = [0] * (N + 1)
    for i in range(1, N + 1):
        bit[i] += 1
        nxt = i + (i & -i)
        if nxt <= N:
            bit[nxt] += bit[i]

    length = 1
    while length <= N:
        length <<= 1
    length >>= 1

    ans = [0] * N

    for x in range(1, N + 1):
        target = A[x - 1] + 1
        idx = 0
        step = length
        while step > 0:
            nxt = idx + step
            if nxt <= N and bit[nxt] < target:
                target -= bit[nxt]
                idx = nxt
            step >>= 1

        pos = idx + 1
        ans[pos - 1] = x

        curr = pos
        while curr <= N:
            bit[curr] -= 1
            curr += curr & -curr

    sys.stdout.write(" ".join(map(str, ans)) + "\n")


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.8-flash-high.