概要

「西から見たときに見えるビル（それまでの最高高さを更新するビル）」の個数を、ちょうど1棟取り壊す操作で最大化する問題です。取り壊す位置によって「新たに見えるようになる区間」が局所的に変わる点がポイントです。

考察

1. 取り壊し前に見えるビル = 「strict な累積最大」

ビル \(i\) が見える条件は
「\(1..i-1\) の最大高さが \(H_i\) 未満」
つまり \(H_i\) がそれまでの最大値を 厳密に 更新することです（同じ高さは遮られて見えない）。

したがって、取り壊し前に見えるビルは - \(H_1 < H_{r_2} < H_{r_3} < \cdots\) を満たす prefix maximum（記録更新） の列（コード中 records）になります。個数を \(k\) とします。

2. 見えないビルを壊すのは「損もし得もしない」

見えないビル \(i\) は、手前に高さ \(H_i\) 以上が存在します。よって \(H_i\) はその時点の累積最大値以下であり、それ以降の累積最大値も増やしません。
つまり、そのビルが存在しても「以降の見える/見えない」は変わりません。

• 見えないビルを壊すと：見えるビルの個数は そのまま \(k\)（壊したビルはもともと数えていない）

よって 見えないビルが1つでもあるなら答えは少なくとも \(k\) で、これが重要な下限になります（コード中 ans = k if k < N else 0）。

3. 得をする可能性があるのは「見えているビル（記録更新ビル）」を壊すときだけ

記録更新ビル（見えているビル）を壊すと、そのビル自身は見えなくなるので \(-1\) ですが、代わりにそのビルの直後の区間で「遮るもの」が弱くなり、新たに見えるビルが増える可能性があります。

ここで重要な観察： - records[j] を壊しても、次の見えるビル records[j+1] は高さがより高いので依然として見えます。 - したがって、影響があるのは 区間 [ (\,records[j],\ records[j+1}\,) ] の中だけです（最後の記録更新ビルなら終端は \(N\)）。

この区間で、壊した後に見える条件は - 手前の最大高さ = 直前の記録更新ビルの高さ（なければ \(0\)） - そこから右へ「strict に最大を更新する」ものが新たに見える

つまりこの区間で必要なのは： - しきい値 \(th\)（直前記録の高さ）より大きい最初の位置 pos - そこから「次により高いビル」へ進む鎖の長さ（見えるビル列の長さ）

素朴に各 records[j] について区間を線形に走査すると最悪 \(O(N^2)\) になり、\(N\le 2\times 10^5\) では間に合いません。

アルゴリズム

手順A：取り壊し前の見えるビル列 records を作る

左から見て「現在の最大値 mx より大きいときだけ見える」ので、1回の走査で作れます。個数を \(k\) とします。

手順B：「次に自分より高いビル」nxt[i]（Next Greater Element）を作る

nxt[i] = \(i\) より右で初めて \(H\) が 厳密に 大きい位置。単調スタックで \(O(N)\)。

この nxt でわかること： - ある位置 pos が見える（＝その時点の最大より高い）なら、 - 次に見えるのは「初めてそれより高い」ビル = nxt[pos] - さらに次は nxt[nxt[pos]] … という 鎖 になります

よって「区間内で見える個数」は nxt の鎖を辿って数えられます。

手順C：nxt の鎖を高速に数える（二分累乗 / ダブリング）

up[p][i] = nxt を \(2^p\) 回適用した先、を作っておくと、 - start から end 未満にとどまる最大ジャンプ回数を \(O(\log N)\) で数えられます。

コードの count_chain(start, end) がそれで、 - start 自体を1個として数え、nxt で end を越えない範囲まで飛びます。

手順D：「しきい値 \(th\) を超える最初の位置」をセグ木で探す

記録更新ビル records[j] を壊したとき、影響区間は - l = records[j] + 1 - end = records[j+1]（なければ \(N\)） しきい値は - th = H[records[j-1]]（なければ \(0\)）

このとき区間 \([l, end)\) で - \(H_i \le th\) の間は見えない - 初めて \(H_i > th\) となる位置 pos が「新たに見える最初のビル」

これを高速に見つけるため、区間最大のセグメント木を作り、 - 「最大値が \(th\) 以下である限り右へ伸ばす」(max_right) ことで - pos（= 初めて最大値が \(th\) を超える位置）を \(O(\log N)\) で求めます

（コードの max_right_leq(l, th) がそれです。）

手順E：各記録更新ビルを壊す場合を評価

各 records[j]=idx について 1. pos を求める（なければ gain=0） 2. gain = count_chain(pos, end)（区間内で新たに見える個数） 3. 取り壊し後の見える数候補： [ (k-1) + gain ] - \(k-1\)：もともと見えていた \(k\) 個から壊した1個を引く - gain：その代わり増える分

最後に最大を取ります。
また、見えないビルが存在するなら「見えないビルを壊して \(k\) を維持」できるので、初期値として ans=k を入れておきます。

計算量

• 時間計算量: \(O(N \log N)\)
  
  • records 作成 \(O(N)\)
  • nxt 作成 \(O(N)\)
  • ダブリング構築 \(O(N \log N)\)
  • セグ木構築 \(O(N)\)
  • 各記録更新ビル（最大 \(N\) 個）について \(O(\log N)\) で探索＋カウント
• 空間計算量: \(O(N \log N)\)（主にダブリング表）

実装のポイント

• 「同じ高さは遮る」ので、可視判定も nxt も 厳密不等号が重要です。
  

  • records は hi > mx
  • nxt は「次に strictly greater」なので、単調スタックでは <= を pop します（while H[st[-1]] <= hi: pop）。

• 記録更新ビル records[j] を壊した影響は、次の記録更新ビルの直前まで（end）に限定されます。ここを間違えると過大に gain を数えてWAになります。

• nxt の終端は存在しない場合 N とし、ダブリングでも N を番兵として扱う（コードの nxt_ext = nxt + [N]）ことで境界処理を簡単にしています。

  ソースコード

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()

---

この解説は gpt-5.2-high によって生成されました。