P3348 [ZJOI2016] The Great Forest

Xiao Y has a great forest at home, containing $n$ trees numbered from $1$ to $n$. Initially, each tree is just a sapling with a single node labeled $1$. Each tree has a special node, called the growth node, which can grow a child node. Xiao Y masters a kind of magic that can make the growth nodes of the $l$-th tree to the $r$-th tree each grow one child node. She can also modify the growth nodes of the $l$-th tree to the $r$-th tree. She told you the log of her magic operations. Can you manage her forest and answer her queries?

The first line contains $2$ positive integers $n, m$, meaning there are $n$ trees and $m$ operations. Then follow $m$ lines. Each line contains several non-negative integers describing one operation, in one of the following formats: `0 l r` Make each growth node of the $l$-th tree to the $r$-th tree grow one child. The label of the new child equals the label generated by the previous operation of type `0` plus $1$ (for example, the first operation of type `0` generates a child with label $2$). The trees from $l$ to $r$ all get a child with the same label. It is guaranteed that $1 \leq l \leq r \leq n$. `1 l r x` Set the growth node of each tree from the $l$-th to the $r$-th to the node labeled $x$. For the $i$-th tree ($l \leq i \leq r$), if the node labeled $x$ is not in that tree, this operation has no effect on that tree. It is guaranteed that $1 \leq l \leq r \leq n$, and $x$ does not exceed the current maximum label among all trees. `2 x u v` Query the distance between node $u$ and node $v$ in the $x$-th tree, i.e., the number of edges on the shortest path between $u$ and $v$ in the $x$-th tree. It is guaranteed that $1 \leq x \leq n$, and nodes $u$ and $v$ exist in this tree.

Output several lines. For each of Xiao Y’s queries, print the answer in order.

For $100\%$ of the testdata, $N \leq 10^5, M \leq 2 \times 10^5$. Translated by ChatGPT 5