Overview

This problem asks us to maximize the number of buildings visible from the west (left side) when exactly one building is demolished from a row of \(N\) buildings.

A naive approach of “trying all buildings to demolish and counting visible buildings each time” would take \(O(N)\) per simulation and \(O(N^2)\) overall, which exceeds the time limit under the constraint \(N \le 2 \times 10^5\) (resulting in TLE).

Instead, by efficiently calculating how the number of visible buildings changes when each building is demolished, we can solve the problem in \(O(N \log N)\) total time complexity.

---

Analysis

1. Conditions for a Building to be Visible

Building \(i\) is visible to Takahashi if and only if “there is no building with height \(H_i\) or greater to the left of building \(i\) (from \(1\) to \(i-1\))”.

Let us define \(C_i\) as the number of buildings to the left of building \(i\) with height \(H_i\) or greater. - When \(C_i = 0\): Building \(i\) is originally visible. - When \(C_i \ge 1\): Building \(i\) is not visible because it is blocked by buildings in front.

2. Effect of Demolishing Building \(k\)

When building \(k\) is demolished, the total number of visible buildings changes as follows:

1. Effect on building \(k\) itself

   • If building \(k\) was originally visible (\(C_k = 0\)), demolishing it decreases the number of visible buildings by \(1\).
   • If it was not originally visible (\(C_k \ge 1\)), there is no decrease from this factor.

2. Effect on other buildings

   • Among buildings \(i\) that were not originally visible, those that were “blocked only by building \(k\)” will become newly visible when building \(k\) is removed.
   • “Blocked only by building \(k\)” means \(C_i = 1\) and the single blocking building is \(k\).
   • Buildings with \(C_i \ge 2\) remain blocked by other buildings even after building \(k\) is demolished, so they do not become visible.

Therefore, if the total number of originally visible buildings is \(V\), the number of visible buildings after demolishing building \(k\) can be expressed as:

\[(\text{visible count after demolition}) = V - (\text{1 if building } k \text{ was originally visible, 0 otherwise}) + (\text{number of buildings that become newly visible by demolishing building } k)\]

If we can efficiently compute this for all \(k\) (\(1 \le k \le N\)), the maximum value is the answer.

---

Algorithm

To efficiently compute \(C_i\) (the number of buildings to the left with height greater than or equal to building \(i\)) for each building \(i\), we use a Fenwick Tree (Binary Indexed Tree, BIT) and coordinate compression.

Step 1: Coordinate Compression

Since building heights \(H_i\) can be as large as \(10^9\), they cannot be directly used as BIT indices. We focus on the number of distinct heights (at most \(N\) types) and convert them to integers from \(1\) to \(U\) (\(U \le N\)) through coordinate compression.

Step 2: Scan from Left to Right and Identify Blocking Buildings

We scan buildings \(i\) (\(0\) to \(N-1\)) from left to right, performing the following operations:

1. Computing \(C_i\), the number of buildings with height \(\ge H_i\)

   • Using the BIT, we find the count of buildings processed so far (i.e., to the left) with height strictly less than \(H_i\). Call this less.
   • Since the total number of buildings to the left is \(i\), the number of buildings with height \(\ge H_i\) is \(C_i = i - \text{less}\).

2. Identifying the blocking building

   • Let max_val be the maximum height among buildings seen so far, and max_idx be the index of that building.
   • If \(C_i = 1\), the single building blocking building \(i\) is the one with the maximum height so far, i.e., max_idx. Therefore, we increment add_count[max_idx] by \(1\).
   • Then, if the current building \(i\)’s height updates max_val, we update max_val and max_idx.

3. Updating the BIT

   • Add the current building’s height to the BIT.

Step 3: Computing the Answer

Compute the total number of originally visible buildings \(V\) (the count of \(i\) where \(C_i = 0\)). For each building \(k\) (\(1 \le k \le N\)), calculate the value after demolishing it, and output the maximum.

---

Complexity

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

  • Sorting for coordinate compression takes \(O(N \log N)\).
  • BIT queries and updates for each building take \(O(\log N)\), so the entire scan takes \(O(N \log N)\).
  • The final aggregation is \(O(N)\).
  • Overall, the complexity is \(O(N \log N)\), which runs in approximately \(0.2\) seconds even for \(N = 2 \times 10^5\).

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

  • The map for coordinate compression, the BIT, and arrays storing information for each building (C, add_count, etc.) use \(O(N)\) memory.

---

Implementation Notes

• Switching between 1-indexed and 0-indexed

  • Using 1-indexed for BIT operations and building numbers (\(1\) to \(N\)) helps reduce bugs. In the implementation code, max_idx and the keys of add_count use 1-indexed building numbers.

• Identifying the blocking building when \(C_i = 1\)

  • When there is exactly one building to the left with height greater than or equal to the current building, that building is necessarily “the tallest building seen so far.” By leveraging this property, we can identify the blocking building by simply maintaining a single variable, without needing complex data structures.

    Source Code

import sys


def solve():
    input = sys.stdin.read
    data = input().split()
    if not data:
        return
    N = int(data[0])
    H = [int(x) for x in data[1 : N + 1]]

    # 座標圧縮
    unique_H = sorted(list(set(H)))
    h_to_compressed = {val: i + 1 for i, val in enumerate(unique_H)}
    compressed_H = [h_to_compressed[x] for x in H]

    U = len(unique_H)
    bit = [0] * (U + 1)

    def add(idx, val):
        while idx <= U:
            bit[idx] += val
            idx += idx & -idx

    def query(idx):
        s = 0
        while idx > 0:
            s += bit[idx]
            idx -= idx & -idx
        return s

    C = [0] * N
    add_count = [0] * (N + 1)

    max_val = 0
    max_idx = -1

    for i in range(N):
        h = compressed_H[i]
        less = query(h - 1)
        c = i - less
        C[i] = c

        if c == 1:
            add_count[max_idx] += 1

        if h > max_val:
            max_val = h
            max_idx = i + 1

        add(h, 1)

    V = sum(1 for c in C if c == 0)

    ans = 0
    for k in range(1, N + 1):
        is_visible = 1 if C[k - 1] == 0 else 0
        val = V - is_visible + add_count[k]
        if val > ans:
            ans = val

    print(ans)


if __name__ == "__main__":
    solve()

---

This editorial was generated by gemini-3.5-flash-thinking.