Overview

This problem asks us to maximize the number of “buildings visible from the west (buildings that update the running maximum height)” by demolishing exactly one building. The key insight is that depending on the position of the demolished building, the “interval where new buildings become visible” changes locally.

Analysis

1. Buildings visible before demolition = “strict prefix maximums”

The condition for building \(i\) to be visible is:
“The maximum height among buildings \(1..i-1\) is less than \(H_i\)”
In other words, \(H_i\) strictly updates the running maximum (buildings of equal height are blocked and not visible).

Therefore, the buildings visible before demolition form a prefix maximum (record-breaking) sequence satisfying: - \(H_1 < H_{r_2} < H_{r_3} < \cdots\) (referred to as records in the code). Let the count be \(k\).

2. Demolishing a non-visible building “neither helps nor hurts”

A non-visible building \(i\) has a building of height \(\geq H_i\) in front of it. Thus \(H_i\) is at most the running maximum at that point, and it does not increase the running maximum for subsequent buildings.
This means whether or not that building exists, the visibility of subsequent buildings does not change.

• Demolishing a non-visible building: the number of visible buildings stays at \(k\) (the demolished building was never counted).

Therefore, if there is at least one non-visible building, the answer is at least \(k\), which serves as an important lower bound (ans = k if k < N else 0 in the code).

3. The only way to gain is by demolishing a “visible building (record-breaking building)”

When a record-breaking (visible) building is demolished, the building itself is no longer visible (\(-1\)), but the “obstruction” weakens in the interval immediately after it, potentially making new buildings visible.

Key observation: - Even if records[j] is demolished, the next visible building records[j+1] has a greater height and thus remains visible. - Therefore, the effect is limited to the interval [ (\,records[j],\ records[j+1]\,) ] only (if it’s the last record-breaking building, the endpoint is \(N\)).

In this interval, the condition for visibility after demolition is: - The running maximum from earlier = the height of the previous record-breaking building (or \(0\) if none exists) - From there, buildings that “strictly update the maximum” going right become newly visible

So what we need for this interval is: - The first position pos with value greater than threshold \(th\) (the height of the previous record) - The length of the chain from there to “the next taller building” (the length of the visible building sequence)

Naively scanning the interval linearly for each records[j] would be \(O(N^2)\) in the worst case, which is too slow for \(N\le 2\times 10^5\).

Algorithm

Step A: Build the visible building sequence records before demolition

Scanning from left, a building is “visible only when greater than the current maximum mx”, so this can be done in a single pass. Let the count be \(k\).

Step B: Build nxt[i] (Next Greater Element) — “next building taller than self”

nxt[i] = the first position to the right of \(i\) where \(H\) is strictly greater. Computed with a monotonic stack in \(O(N)\).

What nxt tells us: - If position pos is visible (= taller than the running maximum at that point), - The next visible building is “the first one taller than it” = nxt[pos] - Then the next after that is nxt[nxt[pos]] … forming a chain

Thus, “the number of visible buildings in an interval” can be counted by following the nxt chain.

Step C: Count the nxt chain efficiently (binary lifting / doubling)

By precomputing up[p][i] = the position reached by applying nxt \(2^p\) times, - We can count the maximum number of jumps from start that stay below end in \(O(\log N)\).

The function count_chain(start, end) in the code does this: - It counts start itself as 1, then jumps via nxt as far as possible without exceeding end.

Step D: Find “the first position exceeding threshold \(th\)” using a segment tree

When record-breaking building records[j] is demolished, the affected interval is: - l = records[j] + 1 - end = records[j+1] (or \(N\) if none exists) The threshold is: - th = H[records[j-1]] (or \(0\) if none exists)

In the interval \([l, end)\): - While \(H_i \le th\), the building is not visible - The first position where \(H_i > th\) is pos, the “first newly visible building”

To find this efficiently, we build a range maximum segment tree and: - “Extend right as long as the maximum is \(\le th\)” (max_right) to - find pos (= the first position where the maximum exceeds \(th\)) in \(O(\log N)\)

(This is max_right_leq(l, th) in the code.)

Step E: Evaluate demolishing each record-breaking building

For each records[j]=idx: 1. Find pos (if it doesn’t exist, gain=0) 2. gain = count_chain(pos, end) (number of newly visible buildings in the interval) 3. Candidate for number of visible buildings after demolition: [ (k-1) + gain ] - \(k-1\): subtract the 1 demolished building from the original \(k\) visible buildings - gain: the additional buildings gained in return

Finally, take the maximum over all candidates.
Also, if there exists a non-visible building, we can “demolish a non-visible building to maintain \(k\)”, so we initialize with ans=k.

Complexity

• Time complexity: \(O(N \log N)\)
  
  • Building records: \(O(N)\)
  • Building nxt: \(O(N)\)
  • Doubling table construction: \(O(N \log N)\)
  • Segment tree construction: \(O(N)\)
  • For each record-breaking building (at most \(N\)): \(O(\log N)\) for search + count
• Space complexity: \(O(N \log N)\) (mainly the doubling table)

Implementation Notes

• Since “equal heights block visibility”, both the visibility check and nxt require strict inequality.
  

  • records uses hi > mx
  • nxt means “next strictly greater”, so the monotonic stack pops with <= (while H[st[-1]] <= hi: pop).

• The effect of demolishing record-breaking building records[j] is limited to just before the next record-breaking building (end). Getting this wrong leads to overcounting gain and WA.

• When nxt doesn’t exist for a position, it’s set to N, and the doubling table also uses N as a sentinel (nxt_ext = nxt + [N] in the code), simplifying boundary handling.

  Source Code

import sys

def main():
    input = sys.stdin.readline
    N = int(input().strip())
    H = list(map(int, input().split()))

    # Visible buildings are strict prefix maxima
    records = []
    mx = 0
    for i, hi in enumerate(H):
        if hi > mx:
            records.append(i)
            mx = hi
    k = len(records)

    # Next greater element (strictly greater)
    nxt = [N] * N
    st = []
    for i in range(N - 1, -1, -1):
        hi = H[i]
        while st and H[st[-1]] <= hi:
            st.pop()
        nxt[i] = st[-1] if st else N
        st.append(i)

    # Binary lifting on nxt
    nxt_ext = nxt + [N]  # sentinel at N
    LOG = (N + 1).bit_length()
    up = [nxt_ext]
    for _ in range(1, LOG):
        prev = up[-1]
        up.append([prev[x] for x in prev])

    # Segment tree for range maximum + max_right for predicate (max <= th)
    NEG_INF = -10**18

    size = 1
    while size < N:
        size <<= 1
    seg = [NEG_INF] * (2 * size)
    seg[size:size + N] = H
    for i in range(size - 1, 0, -1):
        seg[i] = seg[2 * i] if seg[2 * i] >= seg[2 * i + 1] else seg[2 * i + 1]

    def max_right_leq(l: int, th: int) -> int:
        # returns max r in [l, N] s.t. max(H[l:r]) <= th
        if l >= N:
            return N
        sm = NEG_INF
        x = l + size
        while True:
            while (x & 1) == 0:
                x >>= 1
            val = seg[x] if seg[x] >= sm else sm
            if val > th:
                while x < size:
                    x <<= 1
                    val2 = seg[x] if seg[x] >= sm else sm
                    if val2 <= th:
                        sm = val2
                        x += 1
                return x - size
            sm = val
            x += 1
            if (x & -x) == x:
                break
        return N

    def count_chain(start: int, end: int) -> int:
        # number of nodes in nxt-chain starting at start, staying < end
        cur = start
        jumps = 0
        for p in range(LOG - 1, -1, -1):
            nxtp = up[p][cur]
            if nxtp < end:
                cur = nxtp
                jumps += 1 << p
        return jumps + 1

    # If there exists an invisible building, deleting it keeps k visible.
    ans = k if k < N else 0

    # Try deleting each record building
    for j, idx in enumerate(records):
        end = records[j + 1] if j + 1 < k else N
        l = idx + 1
        if l >= end:
            gain = 0
        else:
            th = 0 if j == 0 else H[records[j - 1]]
            pos = max_right_leq(l, th)
            if pos >= end:
                gain = 0
            else:
                gain = count_chain(pos, end)
        ans = max(ans, k - 1 + gain)

    print(ans)

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.2-high.