题解

并查集维护祖先，其余左偏树。

const int N = 1e5 + 5;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	bool vis[N];
	namespace LeftistTree {
		int root, tot;
		struct node {
			int l, r, dis, key, id, rt;
		} t[N];
		void Build() {
			t[0] = (node) {0, 0, -1};
		}
		int Merge(int p, int q) {
			if (!p || !q) return p + q;
			if (!(t[p].key == t[q].key? t[p].id < t[q].id: t[p].key < t[q].key)) swap (p, q);
			t[p].r = Merge(t[p].r, q);
			if (t[t[p].l].dis < t[t[p].r].dis) swap(t[p].l, t[p].r);
			t[p].dis = t[t[p].r].dis + 1;
			return p;
		}
		int Insert (int x) {
			t[++tot] = (node) {0, 0, 0, x, tot, tot};
			return tot;
		}
		int GetRoot (int p) {
			return t[p].rt == p? p: t[p].rt = GetRoot(t[p].rt);
		}
		int DeleteRoot (int p) {
			if (vis[p]) return -1;
			p = GetRoot(p);
			int ans = t[p].key;
			vis[p] = 1;
			t[p].rt = t[t[p].l].rt = t[t[p].r].rt = Merge(t[p].l, t[p].r);
			t[p].l = t[p].r = t[p].dis = 0;
			return ans;
		}
	}
	int n, m;
	int a[N];
	int main () {
		n = Read(), m = Read();
		for (int i = 1; i <= n; i++) a[i] = LeftistTree::Insert(Read());
		for (; m--; ) {
			int op = Read(), p = Read();
			if (op == 1) {
				int q = Read();
				if (vis[p] || vis[q]) continue;
				int Rp = LeftistTree::GetRoot(a[p]), Rq = LeftistTree::GetRoot(a[q]);
				if (Rp != Rq) LeftistTree::t[Rp].rt = LeftistTree::t[Rq].rt = LeftistTree::Merge(Rp, Rq);
			} else {
				printf ("%d\n", LeftistTree::DeleteRoot(a[p]));
			}
		}
		return 0;
	}
}

int main () {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	Main::main();
	return 0;
}