以下代码不加我注释所指的一句可以ac

加了样例都过不了

具体来说出现了1的父亲是5，5的父亲是1的情况

但我都清空了啊/yiw

#include<bits/stdc++.h>
#define eb emplace_back
#define ep emplace
using namespace std;

using ll = long long;
constexpr int N = 4e5 + 5;

mt19937 rnd(3284);

struct Node {
	int val, key, sz, l, r, p, tag;
	void addtag(int x) {
		val = tag = x;
	}
	void init(int x) {
		l = r = p = tag = 0;
		sz = 1, val = x;
		
		key = rnd();			// <-- 
		
	}
} t[N];
int rt, idx, T1, T2, T3, T4;
int New(int v) {
	t[++ idx] = {v, rnd(), 1};
	return idx;
}
void pushup(int x) {
	int l = t[x].l, r = t[x].r;
	t[x].sz = t[l].sz + t[r].sz + 1;
	t[l].p = t[r].p = x;
}
void pushdown(int x) {
	if(t[x].tag) {
		t[t[x].l].addtag(t[x].tag);
		t[t[x].r].addtag(t[x].tag);
		t[x].tag = 0;
	}
} 
void split(int x, int v, int& L, int &R) {
	if(!x) {
		return void(L = R = 0);
	}
	pushdown(x);
	if(t[x].val <= v) {
		L = x;
		split(t[x].r, v, t[x].r, R);
	}
	else {
		R = x;
		split(t[x].l, v, L, t[x].l);
	}
	pushup(x);
}
int merge(int x, int y) {
	if(!x || !y) return x + y;
	if(t[x].key < t[y].key) {
		pushdown(x);
		t[x].r = merge(t[x].r, y), pushup(x);
		return x;
	}
	pushdown(y);
	t[y].l = merge(x, t[y].l), pushup(y);
	return y;
}
int n, m;
void update(int x) {
	if(t[x].p) update(t[x].p);
	pushdown(x);
}
int rnk(int x) {
	update(x);
	int k = t[t[x].l].sz + 1;
	while(t[x].p) {
		if(t[t[x].p].r == x) {
			k += t[t[t[x].p].l].sz + 1;
		}
		x = t[x].p;
	}
	return k;
}
void k_split(int x, int k, int& L, int &R) {
	if(!x) return void(L = R = 0);
	pushdown(x);
	int u = t[t[x].l].sz + 1;
	if(u <= k) {
		L = x;
		k_split(t[x].r, k - u, t[x].r, R);
	}
	else {
		R = x;
		k_split(t[x].l, k, L, t[x].l);
	}
	pushup(x);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> n;
	for(int i = 1; i <= n; ++ i) {
		int x; cin >> x;
		split(rt, x, T1, T2);
		rt = merge(merge(T1, New(x)), T2);
	}
	cin >> m;
	while(m --) {
		int op; cin >> op;
		if(op == 1) {
			int x, v; cin >> x >> v;
			k_split(rt, rnk(x) - 1, T1, T2);
			k_split(T2, 1, T2, T3);
			t[x].init(v);
			rt = merge(T1, T3);
			split(rt, v, T1, T2);
			rt = merge(merge(T1, x), T2);
		}
		if(op == 2) {
			int x; cin >> x;
			update(x);
			cout << t[x].val << '\n';
		}
		if(op == 3) {
			int l, r; cin >> l >> r;
			int m = l + r >> 1;
			split(rt, l - 1, T1, T2);
			split(T2, m, T2, T3);
			if(T2) t[T2].addtag(l - 1);
			split(T3, r, T3, T4);	
			if(T3) t[T3].addtag(r + 1);
			rt = merge(merge(merge(T1, T2), T3), T4);
		}
	}
	return 0;
}