2D传送带

题目描述

来自：USACO 2024 December Contest, Silver

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

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

注意传送带也可以将物品移动到方阵外。一个方格c是不可用的，如果一个放置在方格c上的物品将永远不会离开传送带方阵（即它会永远在方阵中移动）。

初始时，Farmer John 还没有开始建造工厂，所以所有方格都以 "?" 开始。接下来的Q（$ 1 \leq Q \leq 2 \times 10^5 $）天，从第1天开始到第Q天，Farmer John 将选择一个没有传送带的方阵并在该方阵上建造一个传送带。

具体地说，在第i天，Farmer John 将在位置($ r_i,c_i $)（ $ 1 \leq r_i,c_i \leq N $）建造一个类型 $ t_i（ t_i \in { L,R,U,D }) $ 的传送带。输入保证在位置($ r_i,c_i $)没有传送带。

每天过后，请帮助 Farmer John 求出他通过最优地在所有余下的没有传送带的方格上建造传送带可以达到的不可用方格的最小数量。

输入描述

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

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

数据范围：

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

输出描述

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

提示

样例1：

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

RL?
U??
?DL

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

RLR
URR
LDL

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

样例2：

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

RLD
D?U
URL

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