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 翻译