P13675 [GCPC 2023] Japanese Lottery

阿弥陀签（Amida-kuji）是一种在日本流行的彩票游戏，可以用来将 $w$ 个奖品分配给 $w$ 个人。 该游戏由 $w$ 条竖直的线段（称为“腿”）和一些连接相邻腿的水平横杆组成。 每个人从腿的顶部出发，奖品放在腿的底部。 为了确定第 $i$ 个人获得哪个奖品，需要从第 $i$ 条腿的顶部出发，遇到横杆时就切换到相邻的腿，一直走到最底部。 你可以在下图（图 J.1）中看到这个游戏以及如何追踪路径。  :::align{center} 草莓采摘游戏，图片来自 [Nanao Wagatsuma](https://commons.wikimedia.org/wiki/File:%E3%82%A4%E3%83%81%E3%82%B4%E3%81%A4%E3%81%BF%E3%82%B2%E3%83%BC%E3%83%A0%E3%81%A8%E3%81%84%E3%81%86%E5%90%8D%E3%81%AE%E3%81%9F%E3%81%A0%E3%81%AE%E3%81%82%E3%81%BF%E3%81%A0%E3%81%8F%E3%81%98.jpg) ::: 你希望通过移除一些横杆，使得对于每个 $i$，第 $i$ 个人都能获得第 $i$ 个奖品。 由于你不想被发现，你希望移除的横杆数量尽可能少。 :::align{center}  图 J.1：阿弥陀签游戏的可视化。第一个人最终连接到第三个奖品。这也是样例输入 2 在所有连接加上后、未移除任何连接时的状态。要让第 $i$ 个人连接到第 $i$ 个奖品，只需移除第 2、3 条腿之间的两根横杆，以及第 3、4 条腿之间最上方的一根横杆。这是唯一的最优解。 ::: 在本题中，初始游戏没有任何横杆。 然后，横杆会被逐个添加或移除。 每次变化后，你都需要计算，当前状态下，最少需要移除多少根横杆，才能使得对于每个 $i$，第 $i$ 个人获得第 $i$ 个奖品。 注意，通过移除所有横杆总是可以实现这一目标。

输入包含： - 一行，包含三个整数 $w, h, q$（$2 \leq w \leq 20$，$1 \leq h, q \leq 2 \cdot 10^5$），分别表示腿的数量、腿的高度和操作次数。 - 接下来 $q$ 行，每行包含三个整数 $y, x_1, x_2$（$1 \leq y \leq h$，$1 \leq x_1, x_2 \leq w$），表示在高度 $y$ 处、腿 $x_1$ 和 $x_2$ 之间添加或移除一根横杆。如果该位置已有横杆，则移除；否则添加。保证 $x_1$ 和 $x_2$ 是相邻的，即 $|x_1 - x_2| = 1$。 保证任意时刻所有横杆在同一高度的位置都不同。

每次操作后，输出一个整数，表示当前状态下，最少需要移除多少根横杆，才能使得对于每个 $i$，第 $i$ 个人获得第 $i$ 个奖品。

由 ChatGPT 4.1 翻译