← 返回题目列表

AtCoder · awc0091_c

C. 城市规划与道路发展

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

分数: 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