Luogu 🟢 P1950 长方形

題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 P1950 长方形

Problem Statement

題目簡述

給定一個 $n \times m$ 的字元矩陣，. 代表可用格子、* 代表不能被包含的格子。

請計算有多少個沿著格線切出的軸對齊子矩形，能夠完全由 . 組成。

Constraints

約束條件

• $1 \leqslant n,m \leqslant 1000$
• 每個格子為 . 或 *

---

思路：枚舉底邊後轉成柱狀圖問題

如果直接枚舉所有子矩形，需要同時決定上下左右四條邊，複雜度至少是 $\mathcal{O}(n^2m^2)$，肯定不可行。

但我們可以像 85. Maximal Rectangle 或 P4147 玉蟾宫 一樣，透過 枚舉矩形的底邊 將問題轉換為在柱狀圖上的問題。也就是對目前這一橫列(row)維護 heights[j]，表示從這一格往上連續有多少個 .。這樣一來，問題就轉化成：固定底邊後，求柱狀圖中「以這一列為底」的矩形數量。

若再固定橫向區間 $[l, r]$，因為寬度已經被 $[l, r]$ 固定，而高度只能從 $1$ 一直選到這段區間中的最小柱高，因此這個區間能形成的矩形數量為：

$$\min(\text{heights}[l \dots r])$$

因此以這一橫列為底邊的所有矩形數量就是：

$$\sum_{0 \leq l \leq r < m} \min(\text{heights}[l \dots r])$$

所以後面兩種方法，本質上都是在求「柱狀圖所有區間最小值總和」。

方法一：單調棧計數每個高度代表的區間

直接枚舉所有左右端點 $[l, r]$ 的區間，數量會高達 $\mathcal{O}(m^2)$，這在時間上無法接受。

不過換個角度想，既然一橫列中高度的變化最多只有 $\mathcal{O}(m)$ 種，我們可以改為「枚舉每一個位置的高度」，計算它作為區間最小值時，能合法覆蓋到多少個不同的區間，最後再將所有位置的貢獻加總。

確認管轄邊界

先假設所有高度都互不相同。對於當前位置，我們可以向左右兩側擴展，直到遇到比它還矮的柱子為止。也就是找到：

• 左邊界：左邊第一個高度 $<$ 當前高度的位置
• 右邊界：右邊第一個高度 $<$ 當前高度的位置

任何完全落在這兩個開邊界內、且包含當前位置的區間，其區間最小值一定就是當前高度。
如果我們算出合法的左端點數量與右端點數量並將兩者相乘，就能得到「以當前高度為最小值」的區間總數。將這個數量乘上當前高度，就是該位置對最終答案的貢獻。

處理高度相同的情況

重複計算的陷阱

如果陣列中存在相同的高度，上述「向左右擴展直到遇到更小值」的作法，會導致跨越這些相同高度的同一個區間被重複統計多次。

解法：人為打破對稱性，規定其中一個方向的條件必須嚴格。例如在尋找右邊界時，改為尋找「右邊第一個高度 $\le$ 當前高度的位置」。
這樣一來，若一個區間內包含多個相同的最小值，這個區間就一定只會被最右側的那個最小值所「管轄」，從而避免重複計算。

使用單調棧加速

剩下的問題是：如何快速找出每個位置的左右邊界？

我們可以使用單調棧（Monotonic Stack）來維護一個高度單調遞增的索引序列：

• 從左掃描到右，當棧頂元素 $\ge$ 當前高度時不斷彈出，即可求出左邊第一個 $<$ 當前高度的位置。
• 從右掃描到左，當棧頂元素 $>$ 當前高度時不斷彈出，即可求出右邊第一個 $\le$ 當前高度的位置。

如此一來，每一橫列(row)的邊界計算都能在線性時間內完成。

類題

• 3676. Count Bowl Subarrays
• 3878. Count Good Subarrays

複雜度分析

• 時間複雜度：$\mathcal{O}(nm)$。每一直行(column)更新高度一次，再各做兩趟單調棧與一趟貢獻累加，都是線性。
• 空間複雜度：$\mathcal{O}(m)$，忽略輸入或每次讀入一橫列。

方法二：單調棧優化 DP

另一個觀點是：不再直接算每個位置「能管多少區間」，而是改算「每個右端點的總貢獻」。

定義一個狀態：

$$f[i] = \sum_{l=0}^{i} \min(\text{heights}[l \dots i])$$

也就是固定右端點在位置 $i$ 時，所有左端點可形成區間的最小值總和。

接著用單調棧找到位置 $i$ 左邊第一個嚴格更小的位置，記作 $p$。此時所有以 $i$ 結尾的區間，可以自然分成兩群：

1. 左端點在 $[0, p]$ 的區間
   這些區間都會跨過 $p$。由於 $p$ 到 $i$ 之間沒有比目前高度更小的值，所以把右端點從 $p$ 延伸到 $i$，區間最小值不會改變。
   因此這一群的總和，直接等於「右端點在 $p$ 時」的答案，也就是 $f[p]$。

2. 左端點在 $[p+1, i]$ 的區間
   這些區間完全落在 $p$ 的右邊，而該區間內每個高度都不小於目前高度。
   若把目前高度記為 $h_i$，那麼每個區間的最小值都等於 $h_i$；區間數量是 $i-p$ 個，總和就是

   $$h_i \cdot (i-p)$$

把兩群加起來，就得到轉移：

$$f[i] = \begin{cases} h_i \cdot (i+1), & \text{左邊不存在更小值}\\ f[p] + h_i \cdot (i-p), & \text{左邊存在更小值} \end{cases}$$

整個橫列(row)的答案就是：

$$\sum_i f[i]$$

如此一來，每一橫列只需一次線性掃描與一次單調棧維護。

複雜度分析

• 時間複雜度：$\mathcal{O}(nm)$。每一列只做一次高度更新與一次單調棧掃描。
• 空間複雜度：$\mathcal{O}(m)$。需要 heights、f 與 stack。

---

Code

方法一：單調棧計數每個高度代表的區間

def solve():
    n, m = map(int, input().split())
    matrix = [input().strip() for _ in range(n)]

    ans = 0
    heights = [0] * m
    for row in matrix:
        for i, ch in enumerate(row):
            heights[i] = heights[i] + 1 if ch == "." else 0

        L = [0] * m
        R = [m - 1] * m
        st = []
        for i, x in enumerate(heights):
            while st and x <= heights[st[-1]]:
                st.pop()
            # 此時 st[-1] 為左邊第一個高度 < x 的位置，故左邊界為 st[-1] + 1
            L[i] = (st[-1] + 1) if st else 0
            st.append(i)
        st.clear()
        for i in range(m - 1, -1, -1):
            while st and heights[i] < heights[st[-1]]:
                st.pop()
            # 此時 st[-1] 為右邊第一個高度 <= x 的位置，故右邊界為 st[-1] - 1
            R[i] = (st[-1] - 1) if st else m - 1
            st.append(i)

        for i in range(m):
            ans += (i - L[i] + 1) * (R[i] - i + 1) * heights[i]
    print(ans)


if __name__ == "__main__":
    solve()

方法二：單調棧優化 DP

def solve():
    n, m = map(int, input().split())
    matrix = [input().strip() for _ in range(n)]

    ans = 0
    heights = [0] * m

    for row in matrix:
        for i, ch in enumerate(row):
            heights[i] = heights[i] + 1 if ch == "." else 0

        # f[j] = 以 j 為右端點的所有區間最小值總和
        f = [0] * m
        st = []
        for i, h in enumerate(heights):
            while st and h <= heights[st[-1]]:
                st.pop()
            if st:
                # 此時 st[-1] 為左邊第一個高度 < h 的位置
                p = st[-1]
                # 左端點位於 [0, p]，且右端點為 p 的矩形都能繼續延伸到 i 的位置，此部分貢獻為 f[p]
                # 左端點位於 [p+1, i] 的矩形，其高度最大可以為 h，貢獻為 h * (i - p)
                f[i] = f[p] + heights[i] * (i - p)
            else:
                f[i] = heights[i] * (i + 1)
            st.append(i)
        ans += sum(f)
    print(ans)


if __name__ == "__main__":
    solve()