AT_abc420_f [ABC420F] kirinuki

给定一个 $N \times M$ 的网格。每个格子中包含 `.` 或 `#`。 关于每个格子的符号信息由 $N$ 个字符串 $S_1,S_2,\dots,S_N$ 给出，其中 $S_i$ 的第 $j$ 个字符表示从上往下第 $i$ 行、从左往右第 $j$ 列的格子中写的符号。 请你计算有多少个至多包含 $K$ 个格子的矩形区域，且该区域内所有格子均为 `.`。 形式化地，计算满足以下条件的整数四元组 $(l_x,r_x,l_y,r_y)$ 的个数： - $1 \le l_x \le r_x \le N$ - $1 \le l_y \le r_y \le M$ - $(r_x-l_x+1) \times (r_y-l_y+1) \le K$ - 对于所有满足 $l_x \le i \le r_x$ 且 $l_y \le j \le r_y$ 的整数对 $(i,j)$，第 $i$ 行第 $j$ 列的格子中为 `.`。

输入按如下格式从标准输入给出： > $N$ $M$ $K$ > $S_1$ > $S_2$ > $\vdots$ > $S_N$

输出满足条件的矩形区域的个数。

## 样例解释 1 需要计数的 $19$ 个矩形区域如下： - 由 $(l_x,r_x,l_y,r_y) = (1,2,2,3)$ 表示的矩形区域 - 由 $(l_x,r_x,l_y,r_y) = (2,3,1,2)$ 表示的矩形区域 - 由 $(l_x,r_x,l_y,r_y) = (2,2,1,3)$ 表示的矩形区域 - 由 $(l_x,r_x,l_y,r_y) = (1,3,2,2)$ 表示的矩形区域 - $4$ 个仅包含 `.` 的 $1$ 行 $2$ 列的矩形区域 - $4$ 个仅包含 `.` 的 $2$ 行 $1$ 列的矩形区域 - $7$ 个仅包含 `.` 的 $1$ 行 $1$ 列的矩形区域 ## 数据范围 - $N$、$M$、$K$ 均为整数。 - $1 \le N, M \le 5 \times 10^5$ - $1 \le N \times M \le 5 \times 10^6$ - $1 \le K \le N \times M$ - $S_i$ 是长度为 $M$ 的、仅包含 `.` 和 `#` 的字符串。 由 ChatGPT 4.1 翻译