80pts，Wa在#7,8,15,16,17，完全不明白哪里错了，可能有问题的地方：离散化、可撤销并查集、脑抽……

https://www.luogu.com.cn/record/176972926

玄二关。

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
	register int x = 0, f = 1;
	register char c = getchar();
	while(c < '0' || c > '9')
	{
		if(c == '-')f = -1;
		c = getchar();
	}
	while(c <= '9' && c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar();
	}
	return x * f;
}

inline void write(int x)
{
	if(!x)return;
	write(x / 10);
	putchar(x % 10 + '0');
	return;
}

struct query
{
	int op, x, y;
}Q[112000];

struct stk
{
	int x, y;
}st[112100];

int fa[112100], siz[112000], tf[112100];
int top, cnt, ans[112100], len, n, m, a[112100], b[112100], v[112100];
int tot[120100], L, R;

vector <int> son[112100];

bool cmp(int x, int y){return a[x] < a[y];}

int getfa(int x)
{
	while(fa[x] != x)x = fa[x];
	return x;
}

void merge(int x, int y)
{
	x = getfa(x), y = getfa(y);
	if(x == y)
	{
		st[++top].x = st[top].y = 0;
		return;
	}
	if(siz[x] < siz[y])
	{
		swap(x, y);
	}
	siz[x] += siz[y];
	fa[y] = x;
	st[++top].x = x, st[top].y = y;
	tot[x] += tot[y];
	return;
}

void cut()
{
	stk x = st[top--];
	if(x.x)
	{
		siz[x.x] -= siz[x.y];
		tot[x.x] -= tot[x.y];
		fa[x.y] = x.y;
	}
	return;
}

void query(int x)
{
	if(ans[x] != -1)return;
	int a = getfa(Q[x].x);
	if(tot[a] < Q[x].y)
	{
		Q[x].y -= tot[a];
		return;
	}
	for(int i = L;i <= R;i++)
	{
		if(a == getfa(b[i]))
		{
			Q[x].y--;
			if(Q[x].y == 0)
			{
				ans[x] = i;
				return;
			}
		}
	}
	return;
}

void dfs(int x)
{
	if(Q[x].op == 1)
	{
		if(Q[x].x <= n && Q[x].y <= n)merge(Q[x].x, Q[x].y);
		for(int i = 0;i < son[x].size();i++)
		{
			dfs(son[x][i]);
		}
		if(Q[x].x <= n && Q[x].y <= n)cut();
	}
	if(Q[x].op == 2)
	{
		for(int i = 0;i < son[x].size();i++)
		{
			dfs(son[x][i]);
		}
	}
	if(Q[x].op == 3)
	{
		query(x);
		for(int i = 0;i < son[x].size();i++)
		{
			dfs(son[x][i]);
		}
	}
	return;
}

signed main()
{
	n = read(), m = read();
	len = 2000;
	top = 0;
	for(int i = 1;i <= n;i++)
	{
		fa[i] = i;
		siz[i] = 1;
		a[i] = read();
		b[i] = i;
	}
	sort(b + 1, b + n + 1, cmp);
	for(int i = 1;i <= n;i++)
	{
		v[i] = a[b[i]];
	}
	int k = 0;
	for(int i = 1;i <= n;i++)
	{
		a[b[i]] = i;
	}
	for(int i = 1;i <= m;i++)
	{
		Q[i].op = read(), Q[i].x = read();
		ans[i] = -1;
		if(Q[i].op & 1)Q[i].y = read(), tf[i] = i - 1;
		else tf[i] = Q[i].x;
		if(tf[i] > i)tf[i] = i - 1;
		son[tf[i]].push_back(i);
	}
	Q[0].op = 2;
	for(cnt = 1;cnt <= n / len + 5;cnt++)
	{
		L = (cnt - 1) * len + 1, R = cnt * len, top = 0;
		for(int i = 1;i <= n;i++)
		{
			tot[i] = 0;
			fa[i] = i;
			siz[i] = 1;
			if(a[i] >= L && a[i] <= R)tot[i] = 1;
		}
		dfs(0);
	}
	for(int i = 1;i <= m;i++)
	{
		if(Q[i].op == 3)
		{
			if(ans[i] <= m && ans[i] >= 1)cout << v[ans[i]] << "\n";
			else cout << "-1\n";
		}
	}
	return 0;
}