P5064 [Ynoi Easy Round 2014] After This War Ends

Can I really become stronger?  【Even if you don’t want to, I will force you to become stronger.】 Then, thanks for your kindness, I’ll say it directly.  Well... I don’t want to become stronger at all~! 【Then how about this: as long as you come back alive from the battlefield.】 【I can promise you any one request, anything at all.】 Huh?  【Marriage is of course out of the question.】 You said anything...  Desserts... Didn’t you make desserts in the cafeteria before? Then, can you make butter cake?  My older sister... that is, among the seniors, there is someone who, every time she comes back alive from the battlefield, will taste butter cake with a blissful look on her face. So... please. 【Of all things, you picked this...】 【No problem. I’ll make you eat until you throw up.】 【So, you must come back alive.】

You are given a graph. Each vertex has a weight, and initially there are no edges. There are some operations: 1. Add an undirected edge between $x$ and $y$. 2. Revert to the state after the $x$-th operation (note that $x$ can be $0$, which means reverting to the initial state). 3. Query the $y$-th smallest vertex weight among the vertices reachable in the connected component containing $x$. If it does not exist, output $-1$.

The first line contains two integers $n,m$, meaning there are $n$ vertices and $m$ operations. The next line contains $n$ numbers, giving the weight of each vertex. Then follow $m$ lines, each being one of the following three types: `1 x y` `2 x` `3 x y` Their meanings are as described in the statement.

For every operation of type $3$, output one line containing one integer, which is the answer.

Idea: nzhtl1477. Solution: nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time ，$O(n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time , $O( n\log n )$ Space ) , zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space ). Code: nzhtl1477( $O( nm/w )$ Time , $O( n\log n )$ Space )，ccz181078( $O( m\sqrt{n\log n} )$ Time , $O( n\sqrt{n\log n} )$ Space ) ，shadowice1984( $O( m\sqrt{n\log n} )$ Time ，$O( n\log n )$ Space )，zx2003( $O( m\sqrt{n} )$ Time ，$O( n )$ Space ). Data: nzhtl1477( partially uploaded ). Constraints: for $100\%$ of the testdata, $1\leq n,m\leq 10^5$ and $0\leq a_i\leq 10^9$. Translated by ChatGPT 5