{"problem":{"name":"[JOI Open 2018] 山体滑坡 / Collapse","description":{"content":"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$​，他们会拆除一段连接城镇 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":6000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P7"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9598"},"statements":[{"statement_type":"Markdown","content":"I 先生有一个 $C$ 天的电缆建设计划。第 $(i+1)\\ (0\\le i\\le C-1)$​ 天的计划用三个整数 $T_i,X_i,Y_i$ 表示，分别表示：\n\n- 如果 $T_i=0$，他们会架设一段连接城镇 $X_i$ 与城镇 $Y_i$ 的电缆。保证在第 $(i+1)$ 天开始的时候城镇 $X_i$ 与城镇 $Y_i$ 之间没有电缆。\n- 如果 $T_i=1$​，他们会拆除一段连接城镇 $X_i$​ 与城镇 $Y_i$​ 的电缆。保证在第 $(i+1)$​ 天开始的时候城镇 $X_i$​ 与城镇 $Y_i$​ 之间有电缆。\n\nJOI 国经常发生山体滑坡。如果在城镇 $x$ 与 $x+1\\ (0\\le x\\le N-2)$​ 之间发生山体滑坡，则只有连接两端编号均不超过 $x$ 与编号均不少于 $x+1$ 城镇的电缆可用。在 JOI 国，每当山体滑坡发生，他们就会选择一些城镇建设基站。基站应满足对于任意城镇，都可以通过一些可用的电缆与基站连通。\n\nI 先生在建设阶段就在考虑山体滑坡发生时应建设多少基站。他有 $Q$ 个问题：第 $(j+1)$ 个问题用两个整数 $W_j,P_j$ 表示，表示他想知道在 $(W_j+1)$ 天结束时，如果在城镇 $P_j$ 和 $P_j+1$ 之间发生山体滑坡，至少应该建立多少基站。\n\n你作为 I 先生的助理，负责写一个程序去回答 I 先生的问题。\n\n## Input\n\nLOJ 上为交互题，方便起见，这里使用传统题的方式进行评测。\n\n第一行三个整数 $N,C,Q$。\n\n接下来 $C$ 行，每行三个整数 $T_i,X_i,Y_i$。\n\n接下来 $Q$ 行，每行两个整数 $W_j,P_j$。\n\n## Output\n\n输出 $Q$ 行，第 $j+1$ 行输出 $D_j$ 表示对第 $(j+1)$​ 个问题的回答。\n\n[samples]\n\n## Note\n\n**【样例】**\n\n考虑有 $5$ 个城镇的情况。接下来用 $(x,y)$ 代表连接城镇 $x$ 和城镇 $y$ 的电缆。\n\n- 假设当有四根电缆 $(0,1),(1,3),(2,4),(4,0)$ 时，在城镇 $1$ 和 $2$ 之间发生了滑坡。电缆 $(1,3)$ 和 $(4,0)$ 不可用了，因此可用的电缆是 $(0,1)$ 和 $(2,4)$。你需要在城镇 $0,2,3$ 建立基站。最少要建立基站数为 $3$。\n- 假设当有六根电缆 $(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\n**【数据范围】**\n\n本题有四个子任务。子任务分值及附加限制如下表所示：\n\n| 子任务编号 | 分值 |              $N$               |              $C,Q$               |              附加限制              |\n| :--------: | :--: | :----------------------------: | :------------------------------: | :--------------------------------: |\n|    $1$     | $5$  |       $2\\le N\\le 5\\ 000$       |       $1\\le C,Q\\le 5\\ 000$       |                 无                 |\n|    $2$     | $30$ |      $2\\le N\\le 100\\ 000$      |      $1\\le C,Q\\le 100\\ 000$      | 所有 $P_j\\ (0\\le j\\le Q-1)$ 都相等 |\n|    $3$     | $30$ | $2\\le N\\le 100\\ 000$ | $1\\le C,Q\\le 100\\ 000$ |      $T_i=0\\ (0\\le i\\le C-1)$      |\n|    $4$     | $35$ |      $2\\le N\\le 100\\ 000$      |      $1\\le C,Q\\le 100\\ 000$      |                 无                 |","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9598","tags":["2018","JOI（日本）"],"sample_group":[["5 8 2\n0 0 1\n0 1 3\n0 2 4\n0 4 0\n1 1 3\n0 0 3\n0 1 2\n0 4 3\n3 1\n7 3\n","3\n2"]],"created_at":"2026-03-03 11:09:25"}}