AT_arc205_a [ARC205A] 2x2 Erasing

有一个 $N$ 行 $N$ 列的网格。用 $(r,c)$ 表示从上到下第 $r$ 行、从左到右第 $c$ 列的格子。每个格子被染成黑色或白色。当 $S_{r,c}$ 为 `#` 时，格子 $(r,c)$ 被染成黑色；当 $S_{r,c}$ 为 `.` 时，格子 $(r,c)$ 被染成白色。 你会被给出 $Q$ 个关于这个网格的问题，请分别回答每一个问题。在第 $i$ 个问题中（$1 \le i \le Q$），给定整数 $U_i,D_i,L_i,R_i$，请回答如下问题。 - 将所有不满足 $U_i \le r \le D_i$ 且 $L_i \le c \le R_i$ 的格子全部染成黑色后，最多可以执行多少次下述操作？ - 选择一对整数 $(r,c)$，使得格子 $(r,c),(r,c+1),(r+1,c),(r+1,c+1)$ 都为白色，并将这四个格子中的任意一个染成黑色。 注意每个问题独立进行。换言之，每次询问都要从初始状态开始重新计算每个格子的颜色。

输入从标准输入读入，格式如下： > $N$ $Q$ > $S_{1,1}S_{1,2}\ldots S_{1,N}$ > $S_{2,1}S_{2,2}\ldots S_{2,N}$ > $\vdots$ > $S_{N,1}S_{N,2}\ldots S_{N,N}$ > $U_1$ $D_1$ $L_1$ $R_1$ > $U_2$ $D_2$ $L_2$ $R_2$ > $\vdots$ > $U_Q$ $D_Q$ $L_Q$ $R_Q$

输出 $Q$ 行。 第 $i$ 行（$1 \le i \le Q$）应输出第 $i$ 个问题的答案。

## 样例解释 1 以第一个问题为例。 把所有不满足 $1 \le r \le 3$ 且 $1 \le c \le 3$ 的格子全部染成黑色后，网格如下所示： ``` ..### ...## #..## ##### ##### ``` 在该网格上，你可以执行两次操作，具体如下： - 选择 $(r,c)=(1,1)$。在格子 $(1,1),(1,2),(2,1),(2,2)$ 中，任选一个，比如将 $(1,2)$ 染成黑色。 - 选择 $(r,c)=(2,2)$。在格子 $(2,2),(2,3),(3,2),(3,3)$ 中，任选一个，比如将 $(2,2)$ 染成黑色。 无法再执行更多操作，因此第一行输出 $2$。 ## 约束条件 - $2\le N\le 500$ - $1\le Q\le 2\times 10^5$ - $S_{r,c}$ 仅为 `.` 或 `#`。 - $1\le U_i < D_i \le N$ - $1\le L_i < R_i \le N$ - $N,Q,U_i,D_i,L_i,R_i$ 均为整数。 由 ChatGPT 5 翻译