题意理解

有一个 $N \times M$ 的网格，每个格子是 .（可用）或 #（不可用）。

定义合适矩形：该矩形内所有格子都是 .。

每个格子的潜力值 = 包含该格子的合适矩形数量。

求所有格子潜力值之和。

---

核心难点

1. 数据范围大：$N, M \leq 2000$，需要 $O(NM)$ 或 $O(NM \log M)$ 算法
2. 双重计数：既要枚举所有合适矩形，又要计算每个矩形覆盖的格子数
3. 障碍处理：# 会破坏矩形的连续性

---

关键思路：按底边枚举 + 单调栈

第一步：问题转化

总潜力值 = $\sum_{\text{合适矩形}} (\text{矩形面积})$

因为每个合适矩形对它所覆盖的每个格子贡献 $1$。

所以问题转化为：求所有合适矩形的面积和。

---

第二步：按行处理

对于每一行，考虑以该行为矩形底边的情况。

设 $h[j]$ 表示从当前行向上连续 . 的个数（即高度）。

例：
.#..   -> h = [1,0,1,2]
..#.   -> h = [2,1,0,1]

---

第三步：计算一行的贡献

对于固定的底边行，我们需要计算所有以该行为底边的矩形的面积和。

对于每个位置 $j$，考虑以 $(i,j)$ 为右下角的矩形：

设 $L[j]$ 是左边第一个 $h[k] < h[j]$ 的位置，$R[j]$ 是右边第一个 $h[k] \leq h[j]$ 的位置。

那么高度为 $h[j]$ 的矩形在水平方向能延伸的范围是 $(L[j], R[j])$。

---

第四步：面积计算公式

对于高度 $h$，宽度为 $w$ 的矩形，其面积和为：

$$\sum_{i=1}^w \sum_{j=1}^h i \times j = \frac{w(w+1)}{2} \times \frac{h(h+1)}{2} $$

但我们需要更精细的计算：对于每个位置 $j$，它作为矩形右下角时，能形成的高度从 $1$ 到 $h[j]$ 的矩形。

---

第五步：关键公式推导

对于位置 $j$，设：

• $left = L[j] + 1$（矩形左边界+1）
• $right = R[j] - 1$（矩形右边界-1）
• $height = h[j]$

那么包含位置 $j$ 且以当前行为底边的矩形数量为：

$$\sum_{w=1}^{j-left+1} \sum_{h=1}^{height} w \times h = \frac{(j-left+1)(j-left+2)}{2} \times \frac{height(height+1)}{2} $$

但实际上我们需要更高效的方法。

---

算法框架

1. 预处理高度数组

for i = 1 to N:
    for j = 1 to M:
        if grid[i][j] == '.':
            h[j] = h[j] + 1
        else:
            h[j] = 0

2. 单调栈计算左右边界

对于每一行：

• 用单调递增栈求出每个 $h[j]$ 的左右边界 $L[j]$, $R[j]$
• $L[j]$ = 左边第一个 $h[k] < h[j]$ 的位置
• $R[j]$ = 右边第一个 $h[k] \leq h[j]$ 的位置

3. 计算贡献

对于每个 $j$，贡献为：

$$\text{贡献} = h[j] \times (j - L[j]) \times (R[j] - j) \times \frac{(h[j] + 1) \times h[j]}{2} $$

解释：

• $h[j]$：矩形高度
• $(j - L[j]) \times (R[j] - j)$：以 $j$ 为最低点的矩形宽度组合数
• $\frac{h(h+1)}{2}$：高度从 $1$ 到 $h$ 的求和

---

正确性分析

这种计算方法确保了：

1. 每个矩形被其最低的列统计
2. 不会重复计算
3. 障碍物自然形成边界

---

复杂度分析

• 预处理高度：$O(NM)$
• 每行单调栈：$O(M)$
• 总复杂度：$O(NM)$，满足数据范围要求

---

关键代码思路

long long total = 0;
vector<int> h(M+2, 0);

for (int i = 0; i < N; i++) {
    // 更新高度
    for (int j = 0; j < M; j++) {
        if (grid[i][j] == '.') h[j+1]++;
        else h[j+1] = 0;
    }
    
    // 单调栈
    stack<int> st;
    vector<int> L(M+2), R(M+2);
    
    for (int j = 1; j <= M; j++) {
        while (!st.empty() && h[st.top()] >= h[j]) st.pop();
        L[j] = st.empty() ? 0 : st.top();
        st.push(j);
    }
    
    // 清空栈，计算R
    while (!st.empty()) st.pop();
    for (int j = M; j >= 1; j--) {
        while (!st.empty() && h[st.top()] > h[j]) st.pop();
        R[j] = st.empty() ? M+1 : st.top();
        st.push(j);
    }
    
    // 计算贡献
    for (int j = 1; j <= M; j++) {
        if (h[j] == 0) continue;
        long long width = (j - L[j]) * (R[j] - j);
        long long height_sum = (long long)h[j] * (h[j] + 1) / 2;
        total += width * height_sum;
    }
}

---

总结

这道题的核心在于：

1. 问题转化：将潜力值和转化为矩形面积和
2. 按行处理：逐行计算以该行为底的矩形
3. 单调栈：高效求出每个高度的控制范围
4. 组合计数：精确计算每个位置对总和的贡献

通过单调栈优化，我们能在 $O(NM)$ 时间内解决这个看似 $O(N^2M^2)$ 的问题。