AT_abc331_d [ABC331D] Tile Pattern

题目描述

有一个纵横各为 $10^9$ 的网格。第 $i+1$ 行、第 $j+1$ 列的格子（$0 \leq i, j < 10^9$）记作 $(i, j)$。（请注意，这里的下标分配方式与通常不同。）
每个格子要么是黑格，要么是白格。格子 $(i, j)$ 的颜色由字符 $P[i \bmod N][j \bmod N]$ 决定，如果是 B，则 $(i, j)$ 是黑格，如果是 W，则是白格。这里 $a \bmod b$ 表示 $a$ 除以 $b$ 的余数。

给定 $Q$ 个查询，请依次处理。
每个查询给出 $4$ 个整数 $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$

输出格式

请按照题目要求，按顺序输出每个查询的答案，每个答案占一行。

输入输出样例 #1

输入 #1

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

输出 #1

4
7

输入输出样例 #2

输入 #2

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

输出 #2

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 < 10^9$
• $0 \leq B \leq D < 10^9$
• $N, Q, A, B, C, D$ 均为整数

样例解释 1

网格的左上部分如图所示。

对于第 $1$ 个查询，以 $(1, 2)$ 为左上角、$(3, 4)$ 为右下角的矩形区域如图中红色边框所示，该区域内包含 $4$ 个黑格。
对于第 $2$ 个查询，以 $(0, 3)$ 为左上角、$(4, 5)$ 为右下角的矩形区域如图中蓝色边框所示，该区域内包含 $7$ 个黑格。

由 ChatGPT 4.1 翻译