Overview

We reconstruct the original line from \(A_x\), the “number of people taller than themselves standing in front of them” for each height \(x\).

We can reconstruct it by placing people in ascending order of height into the \((A_x+1)\)-th available position from the front, and we use a Fenwick Tree (BIT) to manage the available positions.

Analysis

Placing People in Ascending Order of Height

Initially, prepare \(N\) empty slots for the answer line. Then, consider placing people in the order of heights \(1,2,\dots,N\).

At the moment we place the person of height \(x\):

• All people already placed have heights strictly less than \(x\).
• After placing \(x\), all remaining empty slots will be filled by people taller than \(x\).

Therefore, the number of taller people standing in front of the person of height \(x\) is equal to the number of empty slots remaining before the position where \(x\) is placed.

To make this count equal to \(A_x\), we see that we should place the person of height \(x\) at the \((A_x+1)\)-th empty slot from the front.

Concrete Example

Consider the case where \(N=4\) and \(A=(2,0,1,0)\). Denoting an empty slot as □, they can be placed as follows:

Height to place \(x\)	\(A_x\)	Chosen empty slot	Line after placement
\(1\)	\(2\)	\(3\)rd from front	□ □ 1 □
\(2\)	\(0\)	\(1\)st from front	2 □ 1 □
\(3\)	\(1\)	\(2\)nd from front	2 □ 1 3
\(4\)	\(0\)	\(1\)st from front	2 4 1 3

For example, people of heights \(2\) and \(4\) are in front of the person of height \(1\), which matches the record \(A_1=2\).

Finding Empty Slots Efficiently

If we scan the line from the front to count empty slots every time, placing one person takes up to \(O(N)\) time. This would take \(O(N^2)\) overall, which is too slow for \(N \le 2\times 10^5\).

Therefore, we maintain the following values for each position using a Fenwick Tree:

• Empty position: \(1\)
• Occupied position: \(0\)

Here, the prefix sum up to a certain position represents the number of empty slots in that range. By using binary lifting on the Fenwick Tree, we can find the \(k\)-th empty slot from the front in \(O(\log N)\) time.

Algorithm

1. Prepare an array ans to store the answer.
2. Construct a Fenwick Tree representing the state where all positions are empty, i.e., each position has a value of \(1\).
3. For each \(x=1,2,\dots,N\) in order, perform the following:
   1. Set \(k=A_x+1\).
   2. Using the Fenwick Tree, find the \(k\)-th empty slot from the front.
   3. Place the person of height \(x\) at that position.
   4. Update the value at that position from \(1\) to \(0\).
4. Output ans.

How to Find the \(k\)-th Empty Slot with a Fenwick Tree

The desired position is “the first position where the prefix sum is at least \(k\).”

In the code, we search for pos, which is the position immediately preceding it—that is, “the largest position where the prefix sum is strictly less than \(k\).”

Starting with step as the largest power of \(2\) less than or equal to \(N\) and halving it successively, we perform the following:

• Consider nxt = pos + step as a candidate.
• If nxt <= n and bit[nxt] < k, even skipping this entire range is not enough to reach the target empty slot.
• In that case, update pos = nxt and subtract the number of empty slots in the skipped range from k.

With this search order, bit[nxt] represents the number of empty slots in the range being considered for skipping. After the search finishes, the target position in 1-based indexing is pos + 1.

Correctness

When placing the person of height \(x\), choosing the \((A_x+1)\)-th empty slot from the front ensures that there are exactly \(A_x\) empty slots before them.

Those slots will definitely be filled later by people taller than \(x\). On the other hand, all people already placed are shorter than \(x\), so they are not included in the count \(A_x\).

Thus, the final number of taller people standing in front of the person of height \(x\) will be exactly \(A_x\). Since this holds for all \(x\), the reconstructed line satisfies the condition.

Furthermore, there are \(N-x+1\) empty slots at the time of placing \(x\), and by the constraints \(1 \le A_x+1 \le N-x+1\), the chosen position is guaranteed to exist.

Complexity

• Time Complexity: \(O(N\log N)\)
• Space Complexity: \(O(N)\)

For each person, finding the empty slot and updating the Fenwick Tree both take \(O(\log N)\) time.

Implementation Details

• Initializing the Fenwick Tree in \(O(N)\)
  bit[i] stores the sum of the interval ending at position \(i\) with length i & -i. Since each position initially has a value of \(1\), it can be initialized directly as:

  bit = [i & -i for i in range(n + 1)]
  

• Watch Out for Indexing Differences
  The Fenwick Tree is 1-indexed, while ans is 0-indexed. Since the target position found on the Fenwick Tree is pos + 1, the assignment to the answer array is ans[pos] = x.

• Search Condition is bit[nxt] < k
  If bit[nxt] == k, the desired empty slot lies within that interval. You must not skip the entire interval.

• Subtract \(1\) from the Placed Position
  Add \(-1\) to the corresponding position in the Fenwick Tree so that the occupied position is no longer counted as an empty slot.

  Source Code

import sys


def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    n = data[0]

    bit = [i & -i for i in range(n + 1)]
    ans = [0] * n
    highest_bit = 1 << (n.bit_length() - 1)

    for x in range(1, n + 1):
        k = data[x] + 1
        pos = 0
        step = highest_bit

        while step:
            nxt = pos + step
            if nxt <= n and bit[nxt] < k:
                k -= bit[nxt]
                pos = nxt
            step >>= 1

        ans[pos] = x
        idx = pos + 1
        while idx <= n:
            bit[idx] -= 1
            idx += idx & -idx

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


if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-6-astra-medium.