分数: 366 分
问题陈述
高桥正在调查某城市的建筑物和道路之间的关系。
城市表示为一个网格,其中 H 行和 W 列。牢房位于 i- 从顶部算起的第行 (1 \leq i \leq H)和 j左起第 列 (1 \leq j \leq W) 表示为 (i, j)。每个单元具有以下类型之一:
B:建筑R:道路E:空地
初始状态下,cell的类型 (i, j) 由下式给出 j- 字符串的第一个字符 S_i.
据说一个建筑单元是 面向马路 如果其垂直或水平相邻单元格中的至少一个是道路单元格。对角相邻的单元格不被视为面向道路。
从现在开始, Q 道路施工作业将有序进行。施工的效果是累积的(一旦单元格变成道路,在所有后续操作中它仍然是道路)。
在 k第一次操作 (1 \leq k \leq Q),行中矩形区域内的所有空地块单元格 U_k 到行 D_k 和来自专栏 L_k 转至专栏 R_k 转换为道路单元格。已经是道路或建筑物的单元格不会改变。建筑区域外的单元格也不会发生变化。
确保每个施工操作的矩形区域内不包含任何建筑单元。
每次施工操作后,确定面向道路的建筑单元的总数。即使单个建筑物单元与多个道路单元相邻,它也被算作一个。
约束
- 1 \leq H, W \leq 10^6
- 1 \leq Q \leq 10^5
- H W \leq 2 \times 10^6
- H + Q \leq 2 \times 10^5
- S_i (1 \leq i \leq H) 是一个长度的字符串 W,其中每个字符是以下之一
B,R,或E - 1 \leq U_k \leq D_k \leq H (1 \leq k \leq Q)
- 1 \leq L_k \leq R_k \leq W (1 \leq k \leq Q)
- \displaystyle \sum_{k=1}^{Q} \left( 2(D_k-U_k+1) + 2(R_k-L_k+1) \right) \leq 5 \times 10^6
- 没有单元格
B包含在每个构造操作的矩形区域内 - 所有输入均为整数和字符串
输入
H W Q S_1 S_2 \vdots S_H 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
- 第一行包含整数 H 代表行数, W 代表列数,以及 Q 代表道路施工作业数量,以空格分隔。
- 以下 H 行给出字符串 S_i (1 \leq i \leq H)代表城市的初始状态。的 j- 第一个字符 S_i 代表cell的初始状态 (i, j).
- 以下 Q 行提供道路施工作业的信息。该线代表 k-第一个操作包含顶行号 U_k,底行编号 D_k,左列号 L_k,以及右列号 施工区域的 R_k ,以空格分隔。建筑区域是一个矩形区域,行数为 U_k to D_k (含)和来自 L_k to R_k (含)。
输出
A_1 A_2 \vdots A_Q
输出 Q 行。上 k第行,输出 A_k,紧随其后面向道路的建筑单元总数 k第次施工作业。
示例输入 1
4 5 3 EEEEE EBERE EEEEE REBEE 1 1 1 3 3 4 4 5 2 3 3 3
示例输出 1
1 2 2
示例输入 2
3 3 4 BEB EEE BEB 2 2 2 2 1 3 2 2 2 2 1 3 1 1 2 2
示例输出 2
0 4 4 4
示例输入 3
8 10 7 EEREEEEEER EEBEEEEEEE EEEEERBEEE EEEEEEEEEE BEEEEEEEER EEEEREEEEE EEEEBEEEEE REEEEEEEEE 1 1 1 5 4 4 1 10 2 3 4 6 5 6 2 4 6 8 6 8 1 3 8 10 7 8 1 3
示例输出 3
3 4 4 4 4 4 4
示例输入 4
12 15 10 EEEEREEEEEEEEEE EEEEBEEEREEBEEE EEEEEEEEEEEEEEE EEBEEEEEEEEEEER EREEEEEEEBEEEEE EEEEEEEEEEEEERE EEEEEEBEEEEEEBE EEEEEEEEEEEEEEE BEEEEEEBEEEEEER EEEEREEEEEEEEEE EEEBEEEEEEBEEEE REEEEEEEEEEEEER 1 1 1 15 2 8 1 1 3 6 4 8 2 4 13 15 5 6 11 15 8 10 2 4 10 12 12 15 6 8 8 13 3 3 1 15 12 12 1 15
示例输出 4
3 4 6 6 7 8 9 10 10 10
示例输入 5
1 1 1 E 1 1 1 1
示例输出 5
0