🔗 AWC0096E Mountain Range Vista

Problem Statement

題目簡述

有 $N$ 座山由西向東排成一列，第 $i$ 座山高度為 $H_i$ 。對每個詢問區間 $[L_j,R_j]$ ，從西側往東看這段山脈。

區間中的一座山可見，若它左側同區間內不存在比它嚴格更高的山。等價地，從左到右掃描區間時，每遇到高度不小於目前最大高度的山，就會被看見。請回答每個詢問中可見山的數量。

Constraints

約束條件

$2 \le N \le 2 \cdot 10^5$
$1 \le Q \le 2 \cdot 10^5$
$1 \le H_i \le 10^9$
$1 \le L_j < R_j \le N$
所有輸入皆為整數。

思路：把可見條件轉成支配點統計

直接做法是每個詢問都從左到右掃一遍，維護目前最高高度並計數。但區間長度和詢問數都可達 $2 \cdot 10^5$ ，最壞會到 $\mathcal{O}(NQ)$ ，必須把「一座山是否可見」改寫成能快速查詢的條件。

可見條件的等價轉換

對於某一座山而言，它在某個詢問區間 $[l,r]$ 中是否可見，只取決於它左邊最近的、比它嚴格更高的山在哪裡。

如果這座更高山仍在詢問區間 $[l,r]$ 內，那當前山會被擋住；反之，如果這座更高山在區間左端點外面，或者根本不存在，那麼區間內就沒有任何更高的左側山能擋住它，當前山可見。

定義 $P_i$ 為第 $i$ 座山左側第一座比它嚴格更高的山的位置，若不存在則為 $-1$ 。則第 $i$ 座山在區間 $[l,r]$ 內可見，等價於：

$i \in [l,r]$ ，且
$P_i < l$ ，也就是左側第一座更高的山不在區間內。

為什麼只看最近的更高山就夠？

如果左側存在多座更高山，最近的那座最靠右。只要它已經在區間左端點之外，更左邊的更高山也一定在區間外；如果它在區間內，當前山已經被擋住，不需要再看其他山。

所以問題等價於：對詢問區間 $[l,r]$ ，統計所有位置在 $[l,r]$ 內，且 $P_i < l$ 的山。

如何求左側第一座更高山

這是單調棧的標準用途。從左到右掃描高度，棧中保持高度嚴格遞減的位置。

遇到新山時，所有高度不大於它的棧頂都不可能成為它或後續更高山的「左側第一座更高山」，可以彈出。彈完後，若棧仍非空，棧頂就是左側最近且高度嚴格更高的位置；若棧為空，代表不存在這樣的山。

相同高度不能擋住彼此

題目要求左側存在「嚴格更高」的山才會被擋住，因此高度相同時，新山仍然可見。單調棧中需要彈出小於等於當前高度的位置，留下的才是嚴格更高者。

離線回答詢問

現在每座山都有一個 $P_i$ 。對詢問左端點 $l$ 來說，符合條件的山就是 $P_i < l$ 的那些，再限制位置落在 $[l,r]$ 內。

這是一個二維偏序查詢。把每座山視為點 $(i, P_i)$ ，對詢問 $[l, r]$ ，要統計滿足

l \le i \le r,\quad P_i < l

的點數。

一維是山本身的位置，要查區間 $[l, r]$ 。
另一維是 $P_i$ ，要滿足小於目前詢問的左端點 $l$ 。

可以把所有山按 $P_i$ 排序，所有詢問按左端點排序。當處理到某個左端點時，把 $P_i$ 已經小於它的山加入樹狀陣列(Fenwick Tree)；樹狀陣列按照山的位置記錄是否已加入。此時查詢 $[l, r]$ 的區間中有多少個點，就是答案。

形如「詢問區間內有多少元素滿足某個值小於查詢參數」的問題，常見做法是離線排序：按查詢參數遞增處理，把已滿足條件的元素逐步加入 BIT / Segment Tree，再查位置區間。

正確性說明

對任意詢問區間中的第 $i$ 座山，若 $P_i$ 小於區間左端點，則區間內不存在位於它左側且更高的山，因此它可見。若 $P_i$ 不小於區間左端點，這座更高山就在同一詢問區間內且位於它左側，因此它不可見。

離線處理時，在處理左端點為 $l$ 的詢問前，樹狀陣列中恰好加入了所有 $P_i < l$ 的山；查詢 $[l,r]$ 的位置和，正好統計區間內所有可見山。兩者一一對應，所以答案正確。

複雜度分析

時間複雜度： $\mathcal{O}((N+Q)\log N)$ ，單調棧為 $\mathcal{O}(N)$ ，排序與每次樹狀陣列操作合計為 $\mathcal{O}((N+Q)\log N)$ 。
空間複雜度： $\mathcal{O}(N+Q)$ ，儲存詢問、 $P_i$ 、樹狀陣列與答案陣列。

Code

from atcoder.fenwicktree import FenwickTree


def solve():
    n, q = map(int, input().split())
    H = list(map(int, input().split()))

    queries = []
    for qid in range(q):
        l, r = map(lambda x: int(x) - 1, input().split())
        queries.append((l, r, qid))
    queries.sort()

    # P[i] 表示 H[i] 左側第一個 > H[i] 的位置，若不存在則為 -1
    P = [-1] * n
    st = []
    for i in range(n):
        while st and H[st[-1]] <= H[i]:
            st.pop()
        if st:
            P[i] = st[-1]
        st.append(i)

    points = [(p, idx) for idx, p in enumerate(P)]
    points.sort()

    bit = FenwickTree(n)
    ans = [0] * q

    j = 0
    for l, r, qid in queries:
        while j < n and points[j][0] < l:
            _, idx = points[j]
            bit.add(idx, 1)
            j += 1
        ans[qid] = bit.sum(l, r + 1)  # [l, r]

    print(*ans, sep="\n")


if __name__ == "__main__":
    solve()

寫在最後

Cover Image Credit

The cover image was created by @Qurami. All rights belong to the original artist.

It is used here only as a non-commercial cover illustration for this note. I do not claim ownership of the artwork.

If you are the copyright holder and believe this usage is inappropriate, please contact me by email or leave a comment. I will remove the image promptly.