AT_1_stpc2025_1_i.Subgrid Connected Components

给定一个 $2N+1$ 行 $2N+1$ 列的网格，这里 $N$ 是正整数。网格从上到下的第 $i$ 行、从左到右的第 $j$ 列的格子记作 $(i, j)$，满足 $1 \le i, j \le 2N + 1$。在格子 $(i, j)$ 上写有字符 $S_{i,j}$，且满足以下性质：

• 当 $i$ 为奇数且 $j$ 为奇数时，$S_{i, j} = $ o
• 当 $i$ 为奇数且 $j$ 为偶数时，$S_{i, j} = $ - 或 .
• 当 $i$ 为偶数且 $j$ 为奇数时，$S_{i, j} = $ | 或 .
• 当 $i$ 为偶数且 $j$ 为偶数时，$S_{i, j} = $ .

有 $Q$ 个独立的查询。第 $i$ 个查询（$1 \le i \le Q$）会给定四个奇数 $U_i, D_i, L_i, R_i$，其中 $1 \le U_i \le D_i \le 2N+1,\ 1 \le L_i \le R_i \le 2N+1$，需要解答下述问题：

在子网格 $[U_i, D_i] \times [L_i, R_i]$ 内，以字符 o 为顶点、字符 - 和 | 为边构成的无向图中，连通块（连通分量）的个数是多少？

具体而言，即需要回答下述问题：

考虑一个有 $((D_i - U_i + 2) / 2) \times ((R_i - L_i + 2) / 2)$ 个顶点的无向图 $G$，顶点为所有满足 $U_i \le x \le D_i$ 且 $x$ 为奇数，以及 $L_i \le y \le R_i$ 且 $y$ 为奇数的点对 $(x, y)$。此外，无向图 $G$ 仅包含以下无向边：

• 若 $x$、$y$ 为奇数，且 $U_i \le x \le D_i$，$L_i \le y \le R_i - 2$，并且 $S_{x,y+1} = $ -，则顶点 $(x, y)$ 和 $(x, y+2)$ 之间连有无向边。
• 若 $x$、$y$ 为奇数，且 $U_i \le x \le D_i - 2$，$L_i \le y \le R_i$，并且 $S_{x+1,y} = $ |，则顶点 $(x, y)$ 和 $(x+2, y)$ 之间连有无向边。

试求该无向图 $G$ 的连通块数量。

输入按照以下格式从标准输入读入：

$N$
$S_{1,1}$ $S_{1,2}$ $\cdots$ $S_{1,2N+1}$
$S_{2,1}$ $S_{2,2}$ $\cdots$ $S_{2,2N+1}$
$\vdots$
$S_{2N+1,1}$ $S_{2N+1,2}$ $\cdots$ $S_{2N+1,2N+1}$
$Q$
$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$ 个查询，在第 $i$ 行输出该查询的答案。

注意

本题的内存限制为 384 MiB。

样例解释 1

给定的网格如下所示。

对于第 $1$ 个查询，答案如图所示为 $4$。

数据范围

• $N$ 为整数
• $1 \le N \le 2000$
• 当 $i$、$j$ 为奇数时，$S_{i, j} = $ o
• 当 $i$ 为奇数、$j$ 为偶数时，$S_{i, j} = $ - 或 .
• 当 $i$ 为偶数、$j$ 为奇数时，$S_{i, j} = $ | 或 .
• 当 $i$、$j$ 为偶数时，$S_{i, j} = $ .
• $Q$ 为整数
• $1 \le Q \le 7000$
• $1 \le U_i \le D_i \le 2N+1$
• $1 \le L_i \le R_i \le 2N+1$
• $U_i, D_i, L_i, R_i$ 均为奇数。

由 ChatGPT 5 翻译