长方形

GitHub跳转原题关系图返回列表

逐行构造空白高度，并用单调栈求所有以当前行结底的空白矩形数量。

OJ: luogu

题目 ID: P1950

难度:普及+/提高

标签:单调栈组合计数矩阵python

日期: 2026-07-16 18:25

目录

  1. 题意
  2. 思路
  3. Python 知识
  4. 代码
  5. 复杂度
  6. 总结

题意

统计网格中完全由 . 组成的轴对齐子矩形数量。

思路

逐行维护每列连续空白高度。固定当前行为矩形下边界时，选择一段连续列的可选高度数等于这段高度的最小值，所以要计算直方图所有子数组最小值之和。

递增栈保存 (height, width_count)。弹出更高或相等项时，从 ending_here 中删掉它对所有对应左端点的贡献，并把这些左端点合并给当前高度。每处理一列，ending_here 就是所有以该列结尾矩形数。

Python 知识

  • 直接遍历字节行，. 的字节值是 46，省去字符解码。
  • 栈中把相同高度用 width_count 合并，避免逐个左端点维护。
  • Python 整数可直接保存最多约 101210^{12} 的答案。

代码

python
import sys


input = sys.stdin.buffer.readline
rows, columns = map(int, input().split())
heights = [0] * columns
answer = 0

for _ in range(rows):
    for j, cell in enumerate(input().strip()):
        heights[j] = heights[j] + 1 if cell == 46 else 0

    stack = []
    ending_here = 0
    for height in heights:
        width = 1
        while stack and stack[-1][0] >= height:
            previous_height, previous_width = stack.pop()
            ending_here -= previous_height * previous_width
            width += previous_width
        stack.append((height, width))
        ending_here += height * width
        answer += ending_here

print(answer)

复杂度

时间复杂度 O(nm)O(nm)，空间复杂度 O(m)O(m)。

总结

矩形计数转成“每行直方图的所有子数组最小值之和”。