P3402 可持久化并查集

为啥这开了O2就能过，不开就过不了哇 我看提交记录有好多都是这个情况TAT

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

const int MAXN = 1e5 + 5;
const int MAXM = 2e5 + 5;

int inpt()
{
	int x = 0, f = 1;
	char ch;
	for(ch = getchar(); (ch < '0' || ch > '9') && ch != '-'; ch = getchar());
	if(ch == '-'){
		f = -1;
		ch = getchar();
	}
	do{
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}while(ch >= '0' && ch <= '9');
	return x * f;
}

int n, m;

struct SegmentTree {
	int rt[MAXM];
	
	int l[MAXN << 8], r[MAXN << 8];
	int ls[MAXN << 8], rs[MAXN << 8];
	int dpt[MAXN << 8], fa[MAXN << 8];
	int tot = 0;
	
	int Build(int x, int L, int R) {
		l[x] = L, r[x] = R;
		if(L == R) {
			dpt[x] = 1;
			fa[x] = L;
			
//			cerr<<fa[x]<<endl;
			
			return x;
		}
		int mid = (L + R) >> 1;
		ls[x] = Build(++tot, L, mid);
		rs[x] = Build(++tot, mid + 1, R);
		return x;
	}
	int Change(int x, int lst, int pos, int v) {
		if(l[x] == r[x]) {
			fa[x] = v;
			dpt[x] = dpt[lst];
			return x;
		}
		int mid = (l[x] + r[x]) >> 1;
		if(pos <= mid) {
			l[++tot] = l[ls[lst]], r[tot] = r[ls[lst]];
			ls[x] = Change(tot, ls[lst], pos, v);
			rs[x] = rs[lst];
		}
		if(pos > mid) {
			l[++tot] = l[rs[lst]], r[tot] = r[rs[lst]];
			rs[x] = Change(tot, rs[lst], pos, v);
			ls[x] = ls[lst];
		}
		return x;
	}
	int Ask(int x, int pos) {
		if(l[x] == r[x]) {
			return x;
		}
		int mid = (l[x] + r[x]) >> 1;
		if(pos <= mid) {
			return Ask(ls[x], pos);
		}
		if(pos > mid) {
			return Ask(rs[x], pos);
		}
	}
	
	int GetFa(int ver, int x) {
		int f = Ask(ver, x);
		if(fa[f] == x) {
			return f;
		}else{
			return GetFa(ver, fa[f]);
		}
	}
	
	
	void AddDepth(int x, int pos) {
		if(l[x] == r[x]) {
			dpt[x]++;
			return ;
		}
		int mid = (l[x] + r[x]) >> 1;
		if(pos <= mid) {
			AddDepth(ls[x], pos);
		}
		if(pos > mid) {
			AddDepth(rs[x], pos);
		}
	}
	void Link(int ver, int a, int b) {
		int faa = GetFa(rt[ver - 1], a);
		int fab = GetFa(rt[ver - 1], b);
		
//		cerr<<"fa:"<<fa[faa]<<' '<<fa[fab]<<endl;
//		cerr<<"dpt:"<<dpt[faa]<<' '<<dpt[fab]<<endl;
		
		if(dpt[faa] < dpt[fab]) {
			swap(faa, fab);
		}
		
		l[++tot] = l[rt[ver - 1]], r[tot] = r[rt[ver - 1]];
		rt[ver] = Change(tot, rt[ver - 1], fa[fab], fa[faa]);
		if(dpt[faa] == dpt[fab]) {
			AddDepth(rt[ver], fa[faa]);
		}
		
//		cerr<<"fa:"<<fa[GetFa(rt[ver], a)]<<' '<<fa[GetFa(rt[ver], b)]<<endl;
//		cerr<<"dpt:"<<dpt[GetFa(rt[ver], a)]<<' '<<dpt[GetFa(rt[ver], b)]<<endl;
	}
	
	bool Check(int ver, int a, int b) {
		int faa = GetFa(rt[ver - 1], a);
		int fab = GetFa(rt[ver - 1], b);
		
//		cerr<<"fa: "<<fa[faa]<<' '<<fa[fab]<<endl;
		
		rt[ver] = rt[ver - 1];
		return fa[faa] == fa[fab];
	}
}tr;

int main()
{
	freopen("P3402_11.in", "r", stdin);
	freopen("out.txt", "w", stdout);
	
	n = inpt(), m = inpt();
	
	tr.rt[0] = tr.Build(++tr.tot, 1, n);
	
	for(int i = 1; i <= m; i++) {
//		cerr<<i<<endl;
		
		int op = inpt();
		if(op == 1) {
			int a = inpt(), b = inpt();
			tr.Link(i, a, b);
			continue;
		}
		if(op == 2) {
			int k = inpt();
			tr.rt[i] = tr.rt[k];
			continue;
		}
		if(op == 3) {
			int a = inpt(), b = inpt();
			if(tr.Check(i, a, b)) {
				puts("1");
			}else {
				puts("0");
			}
		}
	}
	
	return 0;
}

虽然大概率是因为我的常数巨大TAT