2D Conveyor Belt

题目描述

农夫约翰的牛奶工厂可以用一个 $N$ 行 $N$ 列（$1 \le N \le 1000$）的网格来描述，网格中的每个格子都可能包含传送带。位置 $(a,b)$ 表示从上往下第 $a$ 行、从左往右第 $b$ 列的格子。 共有 $5$ 种类型的格子： "L"——该格子是一条朝左的传送带，每个时间单位会将其上的所有物品向左移动 1 格。 "R"——该格子是一条朝右的传送带，每个时间单位会将其上的所有物品向右移动 1 格。 "U"——该格子是一条朝上的传送带，每个时间单位会将其上的所有物品向上移动 1 格。 "D"——该格子是一条朝下的传送带，每个时间单位会将其上的所有物品向下移动 1 格。 "?"——农夫约翰还没有在该格子建造传送带。 注意，传送带也可以把物品移动到网格之外。若把一个物品放在格子 $c$ 上，它将永远不会离开传送带网格（即会在网格中一直移动下去），则称格子 $c$ 是不可用的。

起初，农夫约翰还没有开始建造工厂，因此所有格子都是 "?"。接下来从第 $1$ 天到第 $Q$ 天的 $Q$（$1 \le Q \le 2 \cdot 10^5$）天里，农夫约翰每天会选择一个还没有传送带的格子，并在该格子上建造一条传送带。 具体地，在第 $i$ 天，农夫约翰会在位置 $(r_i,c_i)$（$1 \le r_i,c_i \le N$）建造一条类型为 $t_i$（$t_i \in {\text{{L,R,U,D}}}$）的传送带。保证在位置 $(r_i,c_i)$ 原本没有传送带。

在每一天结束后，请帮助农夫约翰求出：在对所有剩余仍未建造传送带的格子进行最优建造的前提下，他能够达到的不可用格子的最小数量。

输入格式

第一行包含 $N$ 和 $Q$。 接下来 $Q$ 行中的第 $i$ 行依次包含 $r_i$、$c_i$ 和 $t_i$。

输出格式

输出 $Q$ 行，第 $i$ 行表示在第 $i$ 天之后，若农夫约翰对当前仍没有传送带的所有剩余格子进行最优建造时，不可用格子的最小数量。

3 5
1 1 R
3 3 L
3 2 D
1 2 L
2 1 U

0
0
0
2
3

3 8
1 1 R
1 2 L
1 3 D
2 3 U
3 3 L
3 2 R
3 1 U
2 1 D

0
2
2
4
4
6
6
9

4 13
2 2 R
2 3 R
2 4 D
3 4 D
4 4 L
4 3 L
4 2 U
3 1 D
4 1 R
2 1 L
1 1 D
1 4 L
1 3 D

0
0
0
0
0
0
0
0
11
11
11
11
13

提示

第五天之后的传送带如下所示。 RL? U?? ?DL 对剩余格子建造传送带的一种最优方案如下。 RLR URR LDL 在该配置下，位置 $(1, 1)$、$(1, 2)$ 和 $(2, 1)$ 的格子是不可用的。

第八天之后的传送带如下所示。 RLD D?U URL 无论农夫约翰在中心格子能建造什么传送带，所有格子都会是不可用的。

计分： 输入 4-5：$N \le 10$ 输入 6-7：$N \le 40$ 输入 8-13：无额外限制 题目作者：Alex Liang

标签: USACO|2024|Silver

来源

USACO|2024|Silver