Overview

\(N\) people stand in a line, and each person throws a ball to the right. The first person taller than the thrower catches it. We need to efficiently compute the total cost of each transfer (the minimum height in the interval from the thrower to the catcher).

Analysis

Problem Formulation

For the ball thrown by person \(i\), we need to determine two things:

1. The catcher \(j\): The leftmost person to the right of \(i\) such that \(H_j > H_i\)
2. The transfer cost: The minimum height in the interval \([i, j]\), i.e., \(\min(H_i, H_{i+1}, \ldots, H_j)\)

Issues with the Naive Approach

For each \(i\), scanning rightward to find \(j\) and then computing the interval minimum takes \(O(N^2)\) time in the worst case, which results in TLE for \(N \leq 2 \times 10^5\).

Strategy for Optimization

We solve the two subproblems efficiently:

1. Next Greater Element: Using a monotonic stack, this can be computed in \(O(N)\) overall.
2. Range Minimum Query: By building a Sparse Table with \(O(N \log N)\) preprocessing, each query can be answered in \(O(1)\).

Concrete Example

For \(H = [3, 1, 4, 1, 5]\):

• \(i=0\) (height 3) → first person to the right taller than 3 is \(j=2\) (height 4) → cost \(= \min(3,1,4) = 1\)
• \(i=1\) (height 1) → \(j=2\) (height 4) → cost \(= \min(1,4) = 1\)
• \(i=2\) (height 4) → \(j=4\) (height 5) → cost \(= \min(4,1,5) = 1\)
• \(i=3\) (height 1) → \(j=4\) (height 5) → cost \(= \min(1,5) = 1\)
• \(i=4\) → no one catches → cost \(= 0\)
• Total \(= 1+1+1+1+0 = 4\)

Algorithm

Step 1: Building the Sparse Table

We build a Sparse Table over the array \(H\). By precomputing \(\text{sparse}[k][i] = \min(H[i], H[i+1], \ldots, H[i+2^k-1])\), we can answer the minimum over any interval \([l, r]\) in \(O(1)\).

\[\text{query\_min}(l, r) = \min(\text{sparse}[k][l],\ \text{sparse}[k][r - 2^k + 1])\]

where \(k = \lfloor \log_2(r - l + 1) \rfloor\).

Step 2: Finding the Next Greater Element with a Monotonic Stack

We scan from left to right, maintaining a stack of “indices whose next greater element has not yet been found.” The stack is kept monotonically decreasing with respect to the values of \(H\).

Each time we encounter a new element \(H[j]\), we compare it with the top of the stack \(H[\text{top}]\). If \(H[\text{top}] < H[j]\), then \(j\) is the Next Greater Element for \(\text{top}\).

Step 3: Summing the Costs

For each \(i\), if a Next Greater Element \(j\) exists, we add \(\text{query\_min}(i, j)\) to the total.

Complexity

• Time complexity: \(O(N \log N)\) (\(O(N \log N)\) for building the Sparse Table, \(O(N)\) for the Next Greater Element, and \(O(1) \times N\) for the queries)
• Space complexity: \(O(N \log N)\) (for storing the Sparse Table)

Implementation Notes

• Monotonic stack condition: Pop when H[stack[-1]] < H[j] (strictly less than). Since equal height does not count as catching, be careful not to include equality in the condition.

• Sparse Table size: Using N.bit_length() to compute \(\log_2 N\) makes the code concise.

• Since \(H[j] > H[i]\), the minimum over the interval \([i, j]\) is effectively the same as \(\min(H[i], H[i+1], \ldots, H[j-1])\). However, including \(H[j]\) does not change the result, so it is fine to take the minimum over the entire interval \([i, j]\).

  Source Code

import sys
from collections import deque

def main():
    input_data = sys.stdin.buffer.read().split()
    N = int(input_data[0])
    H = [int(input_data[i+1]) for i in range(N)]
    
    # For each i, find j = next greater element (strictly greater) to the right
    # Cost = min(H[i], H[i+1], ..., H[j])
    # Since H[j] > H[i], the min of range [i, j] is min(H[i], H[i+1], ..., H[j-1])
    # which equals min(H[i], min(H[i+1..j-1]))
    # But we need an efficient way to compute this.
    
    # Step 1: Find next greater element for each i using a stack
    # Step 2: Compute range minimum queries efficiently using sparse table
    # Step 3: Sum up the costs
    
    # Build sparse table for range minimum queries
    import math
    if N == 0:
        print(0)
        return
    
    LOG = max(1, N.bit_length())
    sparse = [None] * LOG
    sparse[0] = H[:]
    
    for k in range(1, LOG):
        length = 1 << k
        prev = sparse[k-1]
        cur = [0] * N
        for i in range(N - length + 1):
            cur[i] = min(prev[i], prev[i + (1 << (k-1))])
        sparse[k] = cur
    
    def query_min(l, r):
        # min of H[l..r] inclusive
        if l > r:
            return float('inf')
        length = r - l + 1
        k = length.bit_length() - 1
        return min(sparse[k][l], sparse[k][r - (1 << k) + 1])
    
    # Find next greater element using monotonic stack
    # Stack stores indices in decreasing order of H values
    total = 0
    stack = []  # stack of indices, monotonically decreasing in H value
    
    # Process from right to left
    # For each i, we want the smallest j > i such that H[j] > H[i]
    # Using a stack processed left to right:
    
    # Actually, let's process left to right with a stack that helps find next greater
    # Standard next greater element: process left to right, maintain stack of indices
    # whose next greater hasn't been found yet. Stack is monotonically decreasing.
    
    nge = [-1] * N  # next greater element index, -1 if none
    stack = []
    
    for j in range(N):
        while stack and H[stack[-1]] < H[j]:
            i = stack.pop()
            nge[i] = j
        stack.append(j)
    
    # Now compute total cost
    total = 0
    for i in range(N):
        j = nge[i]
        if j == -1:
            continue
        # cost = min(H[i..j])
        total += query_min(i, j)
    
    print(total)

main()

---

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