P14768 [ICPC 2024 Seoul R] Ladder Update

梯子游戏是韩国、中国和日本流行的一种游戏。维基百科称：“它在韩语中被称为 Sadaritagi (사다리타기，字面意思是‘爬梯子’)，在日语中被称为 Amidakuji (阿弥陀籤，意为‘阿弥陀佛抽签’)，在中文中被称为 Guijiaotu (鬼腳圖，字面意思是‘鬼脚图’)。” 进行游戏的图由 $n$ 条垂直线组成，相邻垂直线之间由水平线段连接。这些水平线段被称为 **横档**。每条垂直线都有一个起点（上端）和一个终点（下端）。该游戏的基本规则如下： - 从每条垂直线的起点开始，沿垂直线向下移动。当遇到横档时，沿横档移动到相邻的垂直线，然后继续向下移动，直到到达垂直线的终点。 垂直线从左到右编号为 $1$ 到 $n$。众所周知，游戏结果是 $[1,2,...,n]$ 的一个排列。例如，给定一个有 $4$ 条垂直线和 $5$ 个横档的图（如下所示），从左到右的游戏结果是 $[2,3,4,1]$。 :::align{center}  ::: 然而，有些横档是冗余的，这意味着可以用更少的横档实现相同的结果 $[2,3,4,1]$；如下图所示，只需三个横档（不包括最顶部和最底部的横档）即可获得相同结果。我们希望确定实现相同结果所需的最小水平线段（横档）数量。请注意，如果需要，可以绘制新的横档，而非仅限于给定的那些。 :::align{center}  ::: 你将收到 $q$ 个查询，每个查询要么添加一个新横档，要么删除一个现有横档。请编写一个程序，在处理查询后，输出实现梯子结构相同游戏结果所需的最少横档数量。注意，每个查询是累积的，即每个后续查询都应用于先前查询产生的梯子结构。

你的程序需要从标准输入读取数据。输入的第一行包含三个整数 $n$（垂直线的数量）、$m$（初始横档数量）和 $q$（查询数量），用一个空格分隔，其中 $2 \leq n \leq 100,000$，$1 \leq m \leq 100,000$，$1 \leq q \leq 100,000$。 接下来的 $m$ 行，每行包含两个正整数 $h$ 和 $a$，表示在高度 $h$ 处连接第 $a$ 条和第 $a+1$ 条垂直线的一个横档 ($1 \leq a \leq n-1$)。垂直线从左到右排序，高度从上到下编号，从 $1$ 开始。高度不超过 $10^9$。 接下来的 $q$ 行包含查询信息。每个查询的形式为 $A\ h\ a$ 或 $D\ h\ a$，其中 $1 \leq h \leq 10^9$，$1 \leq a \leq n-1$。 - $A\ h\ a$：在高度 $h$ 处添加一个连接第 $a$ 条和第 $a+1$ 条垂直线的横档。 - $D\ h\ a$：删除在高度 $h$ 处连接第 $a$ 条和第 $a+1$ 条垂直线的横档。 你可以假设没有矛盾的操作，即不会添加已存在的横档，也不会删除不存在的横档。同时，可以假设没有两个横档的位置使得它们在相同高度和相同垂直线共享端点。

你的程序需要向标准输出写入结果。输出包含 $q$ 行，每行包含按输入顺序对应查询所需的实现相同结果的最少横档数量。

**样例 1 解释：** 样例输入 1 给出了初始的梯子结构，如下图所示。游戏结果为 $[3,2,4,1]$。 :::align{center}  ::: 应用第一个查询 $A\ 7\ 1$ 后（如下图所示），梯子结构发生改变，此时游戏结果变为 $[2,3,4,1]$。 :::align{center}  ::: 在五个横档中，只需三个横档（不包括最顶部和最底部的横档）即可实现相同的游戏结果 $[2,3,4,1]$，如下图所示，因此第一个查询的答案是 3。 :::align{center}  ::: 处理第二个查询 $A\ 4\ 3$ 后，梯子结构改变，如下图所示。横档数量无法进一步减少。第二个查询的答案是 6。 :::align{center}  ::: 应用第三个查询 $D\ 3\ 1$ 后，梯子结构改变，如下图所示。 :::align{center}  ::: 如下图所示，具有三个横档的梯子结构可以保证相同的游戏结果，因此第三个查询的答案是 3。 :::align{center}  ::: 翻译由 DeepSeek V3 完成