P9598 [JOI Open 2018] Landslide / Collapse

Mr. I has a $C$-day cable construction plan. The plan for day $(i+1)\ (0\le i\le C-1)$ is given by three integers $T_i, X_i, Y_i$, which mean: - If $T_i=0$, they will install a cable connecting town $X_i$ and town $Y_i$. It is guaranteed that at the beginning of day $(i+1)$, there is no cable between towns $X_i$ and $Y_i$. - If $T_i=1$, they will remove a cable connecting town $X_i$ and town $Y_i$. It is guaranteed that at the beginning of day $(i+1)$, there is a cable between towns $X_i$ and $Y_i$. Landslides often happen in the country of JOI. If a landslide happens between towns $x$ and $x+1\ (0\le x\le N-2)$, then only cables whose two endpoints are both numbered at most $x$, or both numbered at least $x+1$, are usable. In JOI, whenever a landslide happens, they choose some towns to build base stations. The base stations must satisfy that for every town, it can be connected to a base station through some usable cables. During the construction phase, Mr. I is already thinking about how many base stations should be built when a landslide happens. He has $Q$ questions. The $(j+1)$-th question is given by two integers $W_j, P_j$, meaning that he wants to know: after day $(W_j+1)$ ends, if a landslide happens between towns $P_j$ and $P_j+1$, what is the minimum number of base stations that should be built. As Mr. I’s assistant, you are asked to write a program to answer Mr. I’s questions.

On LOJ this is an interactive problem. For convenience, here it is judged in the traditional (non-interactive) way. The first line contains three integers $N, C, Q$. The next $C$ lines each contain three integers $T_i, X_i, Y_i$. The next $Q$ lines each contain two integers $W_j, P_j$.

Output $Q$ lines. The $(j+1)$-th line should output $D_j$, the answer to the $(j+1)$-th question.

**Sample** Consider the case with $5$ towns. In what follows, $(x,y)$ represents a cable connecting town $x$ and town $y$. - Suppose that when there are four cables $(0,1),(1,3),(2,4),(4,0)$, a landslide happens between towns $1$ and $2$. Cables $(1,3)$ and $(4,0)$ become unusable, so the usable cables are $(0,1)$ and $(2,4)$. You need to build base stations in towns $0,2,3$. The minimum number of base stations is $3$. - Suppose that when there are six cables $(0, 1), (0, 3), (1, 2), (2, 4), (4, 0)$ and $(4,3)$, a landslide happens between towns $3$ and $4$. Cables $(2,4),(4,0)$ and $(4,3)$ become unusable, so the usable cables are $(0,1),(0,3)$ and $(1,2)$. You need to build base stations in towns $0$ and $4$. The minimum number of base stations is $2$. **Constraints** This problem has four subtasks. The scores and additional constraints are shown in the table below: | Subtask ID | Score | $N$ | $C,Q$ | Additional Constraints | | :--------: | :--: | :----------------------------: | :------------------------------: | :---------------------------------------------: | | $1$ | $5$ | $2\le N\le 5\ 000$ | $1\le C,Q\le 5\ 000$ | None | | $2$ | $30$ | $2\le N\le 100\ 000$ | $1\le C,Q\le 100\ 000$ | All $P_j\ (0\le j\le Q-1)$ are equal | | $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$ | None | Translated by ChatGPT 5