← 返回题目列表

AtCoder · abc331_d

G. 平铺图案

中文机器翻译题面 查看原题

分数: 450 点

问题陈述

有一个网格 10^9 by 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) 作为右下角。

约束

  • 1 \leq N \leq 1000
  • P[i][j] is W or 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 均为整数。

输入

输入由标准输入按以下格式给出。在这里, \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

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

示例输出 1

4
7

下图显示了网格的左上部分。

image

对于第一个查询,矩形区域 (1, 2) 作为左上角和 (3, 4) 为右下角,被图中红框包围,包含四个黑色方块。
对于第二个查询,矩形区域 (0, 3) 作为左上角和 (4, 5) 为右下角,被图中蓝框包围,包含七个黑色方块。


示例输入 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