P11266 [Template] Meldable Heap 2

Thanks to @[Spasmodic](https://www.luogu.com.cn/user/121027) for providing the first version of the testdata generator. [gen](https://www.luogu.com.cn/paste/4vk36jsp)。

Given positive integers $n$ and $m$, and an integer sequence $a_{1,\dots,n}$ of length $n$. You need to maintain the sequence $a_{1,\dots,n}$ and $n$ sets $S_{1,\dots,n}$. Initially, $S_i=\{i\}$. Then you will perform the following four types of operations for a total of $m$ times. Each operation is in one of these forms: - `0 x y`: Delete element $y$ from set $S_x$. It is guaranteed that $y$ is in $S_x$ at this moment. - `1 x`: Query $\min_{i\in S_x} a_i$. It is guaranteed that $S_x$ is non-empty at this moment. - `2 x y`: Merge set $S_y$ into $S_x$ and clear $S_y$. It is guaranteed that both $S_x$ and $S_y$ are non-empty at this moment, and after this operation there will be no further operations involving set $S_y$. - `3 x y z`: Assign $a_y$ to be $z$. It is guaranteed that $y$ is in $S_x$ at this moment, and $z

The first line contains two positive integers $n$ and $m$. The second line contains $n$ positive integers; the $i$-th positive integer is $a_i$. The next $m$ lines each contain one operation as described above.

For each operation `1`, output one integer per line (note that it is not guaranteed to remain positive) as the answer.

For $20\%$ of the data, $n=m=10$. For $80\%$ of the data, $n=m=10^5$. For $100\%$ of the data, $1\le n,m\le10^6$, $1\le a_i\le2\times10^9$. It is guaranteed that at any time, the absolute value of any element in any heap does not exceed $10^{15}$ (in plain words: each operation `3` decreases a single value by at most $5\times10^8$). --- For the last two test points, the setter’s handwritten heap and the pairing heap in pbds both ran in a few hundred milliseconds. If you are getting constant-factor TLE, you can message privately. Translated by ChatGPT 5