求助 TLE on #3#4#14 1.01s 1.05s 1.20s

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5;
int n, m, root[N << 5], fa[N << 5], dep[N << 5], L[N << 5], R[N << 5], cnt;
#define ls L[rt]
#define rs R[rt]
#define mid ((l+r)>>1)
void read(int& x) {
	x = 0;
	char c; c = getchar();
	while (isdigit(c)) {
		x = (x << 1) + (x << 3) + (c - 48);
		c = getchar();
	}
}
void build(int& rt, int l, int r) {
	rt = ++cnt;
	if (l == r) {
		fa[rt] = l; return;
	}
	build(ls, l, mid);
	build(rs, mid + 1, r);
}
void merge(int last, int& rt, int l, int r, int pos, int p) {
	rt = ++cnt; L[rt] = L[last], R[rt] = R[last];
	if (l == r) {
		fa[rt] = p; dep[rt] = dep[last];
		return;
	}
	if (pos <= mid)merge(L[last], ls, l, mid, pos, p);
	else merge(R[last], rs, mid + 1, r, pos, p);
}
void update(int rt, int l, int r, int pos) {
	if (l == r) {
		dep[rt]++; return;
	}
	if (pos <= mid)update(ls, l, mid, pos);
	else update(rs, mid + 1, r, pos);
}
int query(int rt, int l, int r, int pos) {
	if (l == r)return rt;
	if (pos <= mid)return query(ls, l, mid, pos);
	else return query(rs, mid + 1, r, pos);
}
int find(int rt, int pos) {
	int now = query(rt, 1, n, pos);
	if (fa[now] == pos)return now;
	return find(rt, fa[now]);
}
int main() {
	//scanf("%d%d",&n,&m);
	read(n); read(m);
	build(root[0], 1, n);
	for (int i = 1; i <= m; ++i) {
		int op, a, b, k;//scanf("%d",&op);
		read(op);
		if (op == 1) {
			//scanf("%d%d",&a,&b);
			read(a); read(b);
			root[i] = root[i - 1];
			int pos1 = find(root[i], a), pos2 = find(root[i], b);
			if (fa[pos1] != fa[pos2]) {
				if (dep[pos1] > dep[pos2])swap(pos1, pos2);
				merge(root[i - 1], root[i], 1, n, fa[pos1], fa[pos2]);
				if (dep[pos1] == dep[pos2])update(root[i], 1, n, fa[pos1]);
			}
		}
		else if (op == 2) {
			//scanf("%d",&k);
			read(k);
			root[i] = root[k];
		}
		else {
			//scanf("%d%d",&a,&b);
			read(a); read(b);
			root[i] = root[i - 1];
			int pos1 = find(root[i], a), pos2 = find(root[i], b);
			if (fa[pos1] == fa[pos2])puts("1");
			else puts("0");
		}
	}
	return 0;
}