8853: [yosupo] Data Structure - Persistent Unionfind
[Creator : ]
Description
Let $G_{-1}$ be the graph which consists of $N$ vertices and no edges. Process $Q$ queries in order. The $i$-th query is given with the following format:
- `0 $k_{i}$ $u_{i}$ $v_{i}$`: Let $G\_{i}$ be the graph, which is made by adding an edge $\left( u, v \right)$ to $G\_{k\_{i}}$.
- `1 $k_{i}$ $u_{i}$ $v_{i}$`: If vertices $u, v$ in $G\_{k\_{i}}$ are connected, print $1$. Otherwise, print $0$.
- `0 $k_{i}$ $u_{i}$ $v_{i}$`: Let $G\_{i}$ be the graph, which is made by adding an edge $\left( u, v \right)$ to $G\_{k\_{i}}$.
- `1 $k_{i}$ $u_{i}$ $v_{i}$`: If vertices $u, v$ in $G\_{k\_{i}}$ are connected, print $1$. Otherwise, print $0$.
Input
$N$ $Q$
$t_0$ $k_0$ $u_0$ $v_0$
$\vdots$
$t_{Q-1}$ $k_{Q-1}$ $u_{Q-1}$ $v_{Q-1}$
$t_0$ $k_0$ $u_0$ $v_0$
$\vdots$
$t_{Q-1}$ $k_{Q-1}$ $u_{Q-1}$ $v_{Q-1}$
Constraints
- $1 \leq N \leq 200,000$
- $1 \leq Q \leq 200,000$
- $t\_{i} \in \left \{ 0, 1 \right \}$
- $-1 \leq k_{i} < i$
- for all $k_i$, $k_i = -1$ or $t\_{k_{i}} = 0$ holds.
- $0 \leq u_{i}, v_{i} < N$
- $1 \leq Q \leq 200,000$
- $t\_{i} \in \left \{ 0, 1 \right \}$
- $-1 \leq k_{i} < i$
- for all $k_i$, $k_i = -1$ or $t\_{k_{i}} = 0$ holds.
- $0 \leq u_{i}, v_{i} < N$
Sample 1 Input
5 12
0 -1 0 1
0 0 0 2
1 -1 0 1
1 0 0 1
1 1 0 1
0 1 3 4
0 1 2 3
1 5 1 4
0 5 2 3
1 8 1 4
0 6 3 4
1 10 1 4
Sample 1 Output
0
1
1
0
1
1