Overview

This problem asks us to find the total transfer cost (interval minimum height value) when each person throws a ball to the right and it is caught by the leftmost person who is strictly taller than them.

Analysis

In a naive approach, for each person \(i\), we would linearly search to the right to find the next taller person \(j\), then find the minimum value in the interval \([i, j]\). This method takes \(O(N^2)\) time, which is too slow given that \(N\) can be up to \(2 \times 10^5\).

To solve this efficiently, we need to speed up the following two operations: 1. For each person \(i\), find the next taller person \(j\) (Next Greater Element) 2. Quickly find the minimum value of any interval \([l, r]\) (Range Minimum Query)

Algorithm

1. Computing Next Greater Element:

   • Using a stack, we compute the index of the next greater element for each element in \(O(N)\) time. The stack holds indices, and when the current element is greater than the element at the stack top, we determine that the next greater element of the stack top element is the current element.

2. Preprocessing for Range Minimum Query (RMQ):

   • We build a sparse table. The sparse table requires \(O(N \log N)\) preprocessing time and allows us to answer any interval minimum query in \(O(1)\) time.
   • During preprocessing, we precompute the minimum values for intervals of length \(1, 2, 4, ..., 2^k\).

3. Computing the Cost:

   • For each person \(i\), if a next taller person \(j\) exists, we use RMQ to find the minimum value in the interval \([i, j]\) and add it to the total.

Complexity

• Time complexity: \(O(N \log N)\)
  • Computing Next Greater Element: \(O(N)\)
  • Building the sparse table: \(O(N \log N)\)
  • Query processing: \(O(N)\) (each query is \(O(1)\))
• Space complexity: \(O(N \log N)\)
  • The sparse table uses \(O(N \log N)\) memory

Implementation Notes

• When using the stack, to ensure no unprocessed indices remain, after the loop ends, set the Next Greater Element of any remaining indices in the stack to \(N\) (indicating it does not exist).

• During sparse table preprocessing, a logarithm table is precomputed to efficiently handle intervals of power-of-two lengths.

• When processing queries, the minimum value of the interval \([l, r]\) is found in \(O(1)\) time by comparing the minimum values of two precomputed intervals that cover \([l, r]\).

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    H = list(map(int, data[1:1+n]))
    
    stack = []
    next_greater = [n] * n
    for i in range(n):
        while stack and H[stack[-1]] < H[i]:
            idx = stack.pop()
            next_greater[idx] = i
        stack.append(i)
    
    log_table = [0] * (n + 1)
    for i in range(2, n + 1):
        log_table[i] = log_table[i // 2] + 1
    
    k = log_table[n] + 1
    st = [[0] * n for _ in range(k)]
    st[0] = H[:]
    
    for j in range(1, k):
        step = 1 << (j - 1)
        for i in range(n - (1 << j) + 1):
            st[j][i] = min(st[j - 1][i], st[j - 1][i + step])
    
    def query_min(l, r):
        j = log_table[r - l + 1]
        return min(st[j][l], st[j][r - (1 << j) + 1])
    
    total = 0
    for i in range(n):
        j = next_greater[i]
        if j == n:
            continue
        min_val = query_min(i, j)
        total += min_val
        
    print(total)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.