Overview

A simulation problem where \(N\) dominoes are toppled from left to right in order. To efficiently skip already-fallen dominoes, we use a Union-Find-style data structure that manages “the next standing domino.”

Analysis

Essence of the Problem

Dominoes are toppled by finger from left to right, and according to chain rules, dominoes fall in the rightward direction. For each domino, we need to record “which domino knocked it over.”

Naive Approach and Its Issues

With a straightforward simulation, we would need to linearly search for “the next still-standing domino” for each chain reaction. In the worst case, this becomes \(O(N^2)\), which results in TLE for \(N \leq 5 \times 10^5\).

For example, if the heights are \([5, 4, 3, 2, 1]\), toppling domino 1 causes all dominoes to fall in a chain, but searching for the next standing domino each time is inefficient.

Key to the Solution

Since fallen dominoes never need to be referenced again, we need an operation that “removes from a set and quickly finds the next element.” This can be achieved using a Union-Find technique (with path compression).

Algorithm

1. Prepare the next_standing array: Initialize with next_standing[i] = i (the domino itself is still standing). Set next_standing[N] = N as a sentinel.

2. find_next(x) function: Find the first still-standing domino at position \(x\) or later. Through path compression, it quickly skips over fallen dominoes.

3. mark_fallen(x) function: When domino \(x\) falls, set next_standing[x] = x + 1. The next time find_next visits \(x\), it will automatically search from \(x+1\) onwards.

4. Main loop:

   • Process in order \(i = 0, 1, \ldots, N-1\)
   • Use find_next(i) to check if \(i\) is still standing. If not, skip
   • If standing, topple it by finger (result[i] = 0)
   • Chain processing: Based on the current domino’s height, if the next standing domino’s height is strictly smaller, topple it. The height of the newly toppled domino becomes the new reference

Concrete Example

Input: \(A = [3, 1, 2, 1, 4]\)

• Topple domino 1 (height 3) by finger → Next is domino 2 (height 1), \(1 < 3\) so topple it → Next is domino 3 (height 2), \(2 \geq 1\) so stop
• Domino 2 is already fallen → Skip
• Topple domino 3 (height 2) by finger → Next is domino 4 (height 1), \(1 < 2\) so topple it → Next is domino 5 (height 4), \(4 \geq 1\) so stop
• Domino 4 is already fallen → Skip
• Topple domino 5 (height 4) by finger

Result: 0 1 0 3 0

Complexity

• Time complexity: \(O(N \cdot \alpha(N))\) (nearly \(O(N)\))
  • Each domino falls only once, and mark_fallen is called once per element. find_next runs in amortized constant time due to path compression.
• Space complexity: \(O(N)\)
  • For the next_standing array and the result array.

Implementation Notes

• Path compression: Inside find_next, performing next_standing[x] = next_standing[next_standing[x]] (two-step compression) achieves sufficient speedup without recursion.

• Sentinel: By making next_standing have length \(N+1\) and setting next_standing[N] = N, out-of-bounds checking can be done with the single condition nxt >= N.

• 1-indexed output: Since the problem uses 1-based domino numbering, note that output should use current + 1.

• Height reference during chains: During chains, be careful that “the height of the newly fallen domino” becomes the next reference (not the height of the domino that knocked it over).

  Source Code

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    A = [int(input_data[i + 1]) for i in range(N)]
    
    result = [0] * N
    
    # We process dominoes 1..N in order.
    # For each domino i (0-indexed), if not yet fallen, we push it by hand (result[i]=0),
    # then start a chain: the current domino tries to topple the next standing domino to its right,
    # but only if the next one's height is strictly less than the current one's height.
    #
    # Key insight: when a domino falls, it's removed from the "standing" set.
    # We need to efficiently find the next standing domino to the right.
    # We can use a "next" array (like a linked list / union-find style) to skip fallen dominoes.
    
    # next_standing[i] = the next standing domino index >= i
    # We use path compression similar to union-find
    next_standing = list(range(N + 1))  # next_standing[N] = N means "no more"
    
    def find_next(x):
        while next_standing[x] != x:
            next_standing[x] = next_standing[next_standing[x]]
            x = next_standing[x]
        return x
    
    def mark_fallen(x):
        # Remove x from standing: point x to x+1
        next_standing[x] = x + 1
    
    for i in range(N):
        # Find if domino i is still standing
        pos = find_next(i)
        if pos != i:
            # Already fallen
            continue
        
        # Push domino i by hand
        result[i] = 0
        
        # Start chain from domino i
        current = i
        current_height = A[i]
        mark_fallen(current)
        
        while True:
            # Find next standing domino
            nxt = find_next(current + 1)
            if nxt >= N:
                break
            if A[nxt] < current_height:
                # Topple nxt
                result[nxt] = current + 1  # 1-indexed
                mark_fallen(nxt)
                current = nxt
                current_height = A[nxt]
            else:
                break
    
    sys.stdout.write(' '.join(map(str, result)) + '\n')

main()

---

This editorial was generated by claude4.6opus-thinking.