P9598 [JOI Open 2018] 山体滑坡 / Collapse

I 先生有一个 $C$ 天的电缆建设计划。第 $(i+1)\ (0\le i\le C-1)$​ 天的计划用三个整数 $T_i,X_i,Y_i$ 表示，分别表示： - 如果 $T_i=0$，他们会架设一段连接城镇 $X_i$ 与城镇 $Y_i$ 的电缆。保证在第 $(i+1)$ 天开始的时候城镇 $X_i$ 与城镇 $Y_i$ 之间没有电缆。 - 如果 $T_i=1$​，他们会拆除一段连接城镇 $X_i$​ 与城镇 $Y_i$​ 的电缆。保证在第 $(i+1)$​ 天开始的时候城镇 $X_i$​ 与城镇 $Y_i$​ 之间有电缆。 JOI 国经常发生山体滑坡。如果在城镇 $x$ 与 $x+1\ (0\le x\le N-2)$​ 之间发生山体滑坡，则只有连接两端编号均不超过 $x$ 与编号均不少于 $x+1$ 城镇的电缆可用。在 JOI 国，每当山体滑坡发生，他们就会选择一些城镇建设基站。基站应满足对于任意城镇，都可以通过一些可用的电缆与基站连通。 I 先生在建设阶段就在考虑山体滑坡发生时应建设多少基站。他有 $Q$ 个问题：第 $(j+1)$ 个问题用两个整数 $W_j,P_j$ 表示，表示他想知道在 $(W_j+1)$ 天结束时，如果在城镇 $P_j$ 和 $P_j+1$ 之间发生山体滑坡，至少应该建立多少基站。 你作为 I 先生的助理，负责写一个程序去回答 I 先生的问题。

LOJ 上为交互题，方便起见，这里使用传统题的方式进行评测。 第一行三个整数 $N,C,Q$。 接下来 $C$ 行，每行三个整数 $T_i,X_i,Y_i$。 接下来 $Q$ 行，每行两个整数 $W_j,P_j$。

输出 $Q$ 行，第 $j+1$ 行输出 $D_j$ 表示对第 $(j+1)$​ 个问题的回答。

**【样例】** 考虑有 $5$ 个城镇的情况。接下来用 $(x,y)$ 代表连接城镇 $x$ 和城镇 $y$ 的电缆。 - 假设当有四根电缆 $(0,1),(1,3),(2,4),(4,0)$ 时，在城镇 $1$ 和 $2$ 之间发生了滑坡。电缆 $(1,3)$ 和 $(4,0)$ 不可用了，因此可用的电缆是 $(0,1)$ 和 $(2,4)$。你需要在城镇 $0,2,3$ 建立基站。最少要建立基站数为 $3$。 - 假设当有六根电缆 $(0, 1), (0, 3), (1, 2), (2, 4), (4, 0)$​​ 和 $(4,3)$​​ 时，在城镇 $3$​​ 和 $4$​​ 之间发生了滑坡。电缆 $(2,4),(4,0)$​​ 和 $(4,3)$​​ 不可用了，因此可用的电缆是 $(0,1),(0,3)$​​ 和 $(1,2)$​​。你需要在城镇 $0$​​ 和 $4$ 建立基站。最少要建立基站数为 $2$​​。 **【数据范围】** 本题有四个子任务。子任务分值及附加限制如下表所示： | 子任务编号 | 分值 | $N$ | $C,Q$ | 附加限制 | | :--------: | :--: | :----------------------------: | :------------------------------: | :--------------------------------: | | $1$ | $5$ | $2\le N\le 5\ 000$ | $1\le C,Q\le 5\ 000$ | 无 | | $2$ | $30$ | $2\le N\le 100\ 000$ | $1\le C,Q\le 100\ 000$ | 所有 $P_j\ (0\le j\le Q-1)$ 都相等 | | $3$ | $30$ | $2\le N\le 100\ 000$ | $1\le C,Q\le 100\ 000$ | $T_i=0\ (0\le i\le C-1)$ | | $4$ | $35$ | $2\le N\le 100\ 000$ | $1\le C,Q\le 100\ 000$ | 无 |