主席树 WA80tps，求掉，玄关

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define il inline
#define fr(i,a,b) for(int i=a;i<=b;++i)
#define Fr(i,a,b) for(int i=a;i>=b;--i)
char buf[1048576],*p1 = buf,*p2 = buf, ubuf[1048576],*u = ubuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1048576,stdin),p1==p2)?EOF:*p1++)
inline int read() {
	int x = 0, f = 1;
	char ch = getchar();
	for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
	for (; isdigit(ch); ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
	return x * f;
}
const int N = 5e5 + 5, inf = 2147483647;
int n, op[N], qv[N], qx[N], lsh[N], tot, ans;
int rt[N], s[N << 6], ls[N << 6], rs[N << 6], mx[N << 6], mn[N << 6], cnt;
il void U(int p, int &k, int l, int r, int x, int v) {
	if (!k) k = ++cnt;
	if (l == r) {
		s[k] = max(0, s[k] + v);
		if (s[k]) mx[k] = mn[k] = l;
		else mx[k] = -inf, mn[k] = inf;
		return;
	}
	int m = l + r >> 1;
	if (x <= m) rs[k] = rs[p], U(ls[p], ls[k], l, m, x, v);
	else ls[k] = ls[p], U(rs[p], rs[k], m + 1, r, x, v);
	s[k] = s[ls[k]] + s[rs[k]];
	mx[k] = max(mx[ls[k]], mx[rs[k]]);
	mn[k] = min(mn[ls[k]], mn[rs[k]]);
}
il int S(int k, int l, int r, int x) {
	if (!k) return 0;
	if (r <= x) return s[k];
	int m = l + r >> 1;
	if (m < x) return s[ls[k]] + S(rs[k], m + 1, r, x);
	return S(ls[k], l, m, x);
}
il int Q(int k, int l, int r, int x) {
	if (!k) return 0;
	if (l == r) return l;
	int m = l + r >> 1;
	if (s[ls[k]] >= x) return Q(ls[k], l, m, x);
	return Q(rs[k], m + 1, r, x - s[ls[k]]);
}
il int Mx(int k, int l, int r, int x, int y) {
	if (!k) return -inf;
	if (x <= l && r <= y) return mx[k];
	int m = l + r >> 1;
	if (y <= m) return Mx(ls[k], l, m, x, y);
	if (m < x) return Mx(rs[k], m + 1, r, x, y);
	return max(Mx(ls[k], l, m, x, y), Mx(rs[k], m + 1, r, x, y));
}
il int Mn(int k, int l, int r, int x, int y) {
	if (!k) return inf;
	if (x <= l && r <= y) return mn[k];
	int m = l + r >> 1;
	if (y <= m) return Mn(ls[k], l, m, x, y);
	if (m < x) return Mn(rs[k], m + 1, r, x, y);
	return min(Mn(ls[k], l, m, x, y), Mn(rs[k], m + 1, r, x, y));
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	n = read(), mn[0] = inf, mx[0] = -inf;
	fr(i, 1, n) qv[i] = read(), op[i] = read(), qx[i] = read();
	fr(i, 1, n) if (op[i] != 4) lsh[++tot] = qx[i];
	sort(lsh + 1, lsh + tot + 1), tot = unique(lsh + 1, lsh + tot + 1) - lsh - 1;
	fr(i, 1, n) if (op[i] != 4) qx[i] = lower_bound(lsh + 1, lsh + tot + 1, qx[i]) - lsh;
	fr(i, 1, n) {
		if (op[i] >= 3) rt[i] = rt[qv[i]];
		if (op[i] == 1) U(rt[qv[i]], rt[i], 1, tot, qx[i], 1);
		else if (op[i] == 2) U(rt[qv[i]], rt[i], 1, tot, qx[i], -1);
		else if (op[i] == 3) cout << S(rt[i], 1, tot, qx[i] - 1) + 1 << endl;
		else if (op[i] == 4) cout << lsh[Q(rt[i], 1, tot, qx[i])] << endl;
		else if (op[i] == 5) {
			ans = Mx(rt[i], 1, tot, 1, qx[i] - 1);
			cout << ((ans == -inf) ? ans : lsh[ans]) << endl;
		} else if (op[i] == 6) {
			ans = Mn(rt[i], 1, tot, qx[i] + 1, tot);
			cout << ((ans == inf) ? ans : lsh[ans]) << endl;
		}
	}
	return 0;
}