Problem 3. 2D Conveyor Belt

USACO 2024 December Contest, Silver

Farmer John 的牛奶工厂可以用一个 $N \times N$（$1 \le N \le 1000$）的方阵来表示，其中的方格带有传送带。位置 $(a, b)$ 描述了位于从上往下第 $a$ 行、从左往右第 $b$ 列的方格。有 $5$ 种类型的方格：

1. "L" — 该方格是一个向左的传送带，每一单位时间会将所有物品向左移动一格。
2. "R" — 该方格是一个向右的传送带，每一单位时间会将所有物品向右移动一格。
3. "U" — 该方格是一个向上的传送带，每一单位时间会将所有物品向上移动一格。
4. "D" — 该方格是一个向下的传送带，每一单位时间会将所有物品向下移动一格。
5. "?" — Farmer John 还没有在该方格上建造传送带。

注意传送带也可以将物品移动到方阵外。一个方格 $c$ 是

不可用的

，如果一个放置在方格 $c$ 上的物品将

永远

不会离开传送带方阵（即它会永远在方阵中移动）。

初始时，Farmer John 还没有开始建造工厂，所以所有方格都以 "?" 开始。接下来的 $Q$（$1 \le Q \le 2 \cdot 10^5$）天，从第 $1$ 天开始到第 $Q$ 天，Farmer John 将选择一个

没有

传送带的方阵并在该方阵上建造一个传送带。

具体地说，在第 $i$ 天，Farmer John 将在位置 $(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)$ 没有传送带。

每天过后，请帮助 Farmer John 求出他通过

最优地

在所有

余下的

没有传送带的方格上建造传送带可以达到的不可用方格的最小数量。

输入格式（从终端 / 标准输入读入）：

输入的第一行包含 $N$ 和 $Q$。

以下 $Q$ 行，第 $i$ 行依次包含 $r_i$，$c_i$ 和 $t_i$。

输出格式（输出至终端 / 标准输出）：

输出 $Q$ 行，每行包含 Farmer John 最优地在所有余下的没有传送带的方格上建造传送带时不可用方格的最小数量。

输入样例：

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

输出样例：

0
0
0
2
3

第五天过后的传送带如下所示。

RL?
U??
?DL

一种在余下的方格上建造传送带的最优方案如下。

RLR
URR
LDL

在这种配置下，位于 $(1, 1)$，$(1, 2)$ 和 $(2, 1)$ 的方格是不可用的。

输入样例：

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

第八天过后的传送带如下所示。

RLD
D?U
URL

无论 Farmer John 在中间建造何种传送带，所有方格都将是不可用的。

输入样例：

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

测试点性质： 测试点 4-5：$N \le 10$。测试点 6-7：$N \le 40$。测试点 8-13：没有额外限制。

供题：Alex Liang