Tile Pattern

题目描述

有一个 $10^9$ 乘 $10^9$ 的格子。令 $(i, j)$ 表示从上往下第 $(i + 1)$ 行、从左往右第 $(j + 1)$ 列的格子 $(0 \leq i, j \lt 10^9)$。（注意不寻常的下标分配。）
每个格子是黑色或白色。格子 $(i, j)$ 的颜色由字符 $P[i \bmod N][j \bmod N]$ 表示，其中 $B$ 表示黑色，$W$ 表示白色。这里，$a \bmod b$ 表示 $a$ 除以 $b$ 的余数。 回答 $Q$ 个查询。
每个查询给出四个整数 $A, B, C, D$，要求你求以 $(A, B)$ 为左上角、$(C, D)$ 为右下角的矩形区域中黑色格子的数量。

输入格式

输入从标准输入按以下格式给出。这里，$\text{query}_i$ 是要处理的第 $i$ 个查询。 $N$ $Q$ $P[0][0]P[0][1]\dots P[0][N-1]$ $P[1][0]P[1][1]\dots P[1][N-1]$ $\vdots$ $P[N-1][0]P[N-1][1]\dots P[N-1][N-1]$ $\text{query}_1$ $\text{query}_2$ $\vdots$ $\text{query}_Q$

每个查询按以下格式给出： $A$ $B$ $C$ $D$

输出格式

按照题目描述输出每个查询的答案，答案之间用换行分隔。

3 2
WWB
BBW
WBW
1 2 3 4
0 3 4 5

4
7

10 5
BBBWWWBBBW
WWWWWBBBWB
BBBWBBWBBB
BBBWWBWWWW
WWWWBWBWBW
WBBWBWBBBB
WWBBBWWBWB
WBWBWWBBBB
WBWBWBBWWW
WWWBWWBWWB
5 21 21 93
35 35 70 43
55 72 61 84
36 33 46 95
0 0 999999999 999999999

621
167
44
344
500000000000000000

提示

$1 \leq N \leq 1000$ $P[i][j]$ 是 $W$ 或 $B$。 $1 \leq Q \leq 2 \times 10^5$ $0 \leq A \leq C \lt 10^9$ $0 \leq B \leq D \lt 10^9$ $N, Q, A, B, C, D$ 都是整数。下图说明了格子的左上部分。 对于第一个查询，以 $(1, 2)$ 为左上角、$(3, 4)$ 为右下角的矩形区域（图中红色框所示）包含四个黑色格子。
对于第二个查询，以 $(0, 3)$ 为左上角、$(4, 5)$ 为右下角的矩形区域（图中蓝色框所示）包含七个黑色格子。

标签: AtCoder|abc331D

来源

AtCoder|abc331D