P3402 可持久化平衡树

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

const int MAXN = 5e5 + 5;
const int INF = 1ll * (1 << 31) - 1;
const int INCF = -1ll * (1 << 31) + 1;

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;

mt19937 rd(60505);

struct Point {
	int ls, rs;
	int dat, val;
	int siz;
};
struct PersistenceSplitTreap {
	Point tr[MAXN * 50];
	int root[MAXN];
	int id = 0;
	
	int NewPoint(int v) {
		++id;
		
//		cerr << id << endl;
		
		tr[id].ls = tr[id].rs = 0;
		tr[id].dat = rd();
		tr[id].val = v;
		tr[id].siz = 1;
		return id;
	}
	void Update(int rt) {
		tr[rt].siz = tr[tr[rt].ls].siz + tr[tr[rt].rs].siz + 1;
	}
	
	void Print(int rt) {
		if(!rt) {
			return ;
		}
		Print(tr[rt].ls);
		cerr<<"-----------------------这是一条分割线-----------------------\n";
		cerr<<"root: "<<rt<<endl;
		cerr<<"lson: "<<tr[rt].ls<<endl;
		cerr<<"rson: "<<tr[rt].rs<<endl;
		cerr<<"size: "<<tr[rt].siz<<endl;
		cerr<<"value: "<<tr[rt].val<<endl;
		cerr<<"-----------------------这是一条分割线-----------------------\n";
		Print(tr[rt].rs);
	}
	
	void SplitByVal(int rt, int v, int &l, int &r) {
		if(!rt) {
			l = r = 0;
			return ;
		}
		
		if(tr[rt].val <= v) {
			l = NewPoint(0);
			tr[l] = tr[rt];
			SplitByVal(tr[rt].rs, v, tr[l].rs, r);
			Update(l);
		}
		if(tr[rt].val > v) {
			r = NewPoint(0);
			tr[r] = tr[rt];
			SplitByVal(tr[rt].ls, v, l, tr[r].ls);
			Update(r);
		}
	}
	void Split(int rt, int v, int &l, int &r) {
		if(!rt) {
			l = r = 0;
			return ;
		}
		
		if(tr[rt].val <= v) {
			l = rt;
			SplitByVal(tr[rt].rs, v, tr[l].rs, r);
		}
		if(tr[rt].val > v) {
			r = rt;
			SplitByVal(tr[rt].ls, v, l, tr[r].ls);
		}
		Update(rt);
	}
	int Merge(int l, int r) {
		if((l & r) == 0) return l | r;
		
//		cerr << l << ' ' << r << endl;
		
		int rt = NewPoint(0);
		if(tr[l].dat >= tr[r].dat) {
			tr[rt] = tr[l];
			tr[rt].rs = Merge(tr[l].rs, r);
			Update(rt);
		}
		if(tr[l].dat < tr[r].dat) {
			tr[rt] = tr[r];
			tr[rt].ls = Merge(l, tr[r].ls);
			Update(rt);
		}
		return rt;
	}
	int MergeWithNoNewPoints(int l, int r) {
		if((l & r) == 0) return l | r;
		int rt = 0;
		if(tr[l].dat >= tr[r].dat) {
			rt = l;
			tr[rt].rs = Merge(tr[l].rs, r);
		}
		if(tr[l].dat < tr[r].dat) {
			rt = r;
			tr[rt].ls = Merge(l, tr[r].ls);
		}
		Update(rt);
		return rt;
	}
	
	int Insert(int rt, int v) {
		int l = 0, r = 0;
		SplitByVal(rt, v, l, r);
		return Merge(Merge(l, NewPoint(v)), r);
	}
	int Erase(int rt, int v) {
		int x = 0, y = 0, z = 0;
		SplitByVal(rt, v, x, z);
		SplitByVal(x, v - 1, x, y);
		y = Merge(tr[y].ls, tr[y].rs);
		
//		cerr<<"!!!!!!!!!   "<<y<<endl;
		
		return Merge(Merge(x, y), z);
	}
	
	int GetRankByVal(int rt, int v) {
		int l = 0, r = 0;
		Split(rt, v - 1, l, r);
		int val = tr[l].siz;
		MergeWithNoNewPoints(l, r);
		return val + 1;
	}
	int GetValByRank(int rt, int rk) {
		if(tr[tr[rt].ls].siz + 1 == rk) {
			return tr[rt].val;
		}
		
		if(tr[tr[rt].ls].siz + 1 > rk) {
			GetValByRank(tr[rt].ls, rk);
		}else {
			GetValByRank(tr[rt].rs, rk - tr[tr[rt].ls].siz - 1);
		}
	}
	
	int GetPre(int rt, int v) {
		int l = 0, r = 0;
		Split(rt, v - 1, l, r);
		int val = tr[l].val;
		MergeWithNoNewPoints(l, r);
		return val ? val : INF;
	}
	int GetNext(int rt, int v) {
		int l = 0, r = 0;
		Split(rt, v, l, r);
		int val = tr[r].val;
		MergeWithNoNewPoints(l, r);
		return val ? val : INF;
	}
}pstr;

int main()
{
//	freopen("P3835_3.in", "r", stdin);
//	freopen("out.txt", "w", stdout);
	
	int n = inpt();
	for(int i = 1; i <= n; i++) {
		int ver = inpt();
		int op = inpt();
		int v = inpt();
		if(op == 1) {
			pstr.root[i] = pstr.Insert(pstr.root[ver], v);
			
//			cerr<<pstr.tr[pstr.root[i]].val<<endl;
//			cerr<<i<<": \n";
//			pstr.Print(pstr.root[i]);
			
			continue;
		}
		if(op == 2) {
			pstr.root[i] = pstr.Erase(pstr.root[ver], v);
			
//			cerr<<pstr.tr[pstr.root[i]].val<<endl;
//			cerr<<i<<": \n";
//			pstr.Print(pstr.root[i]);
			
			continue;
		}
		if(op == 3){
			pstr.root[i] = pstr.root[ver];
			
//			cerr<<pstr.tr[pstr.root[i]].val<<endl;
//			cerr<<i<<": \n";
//			pstr.Print(pstr.root[i]);
			
			int x = pstr.GetRankByVal(pstr.root[i], v);
			printf("%d\n", x); 
			continue;
		}
		if(op == 4) {
			pstr.root[i] = pstr.root[ver];
			
//			cerr<<pstr.tr[pstr.root[i]].val<<endl;
//			cerr<<i<<": \n";
//			pstr.Print(pstr.root[i]);
			
			int x = pstr.GetValByRank(pstr.root[i], v);
			printf("%d\n", x); 
			continue;
		}
		if(op == 5) {
			pstr.root[i] = pstr.root[ver];
			
//			cerr<<pstr.tr[pstr.root[i]].val<<endl;
//			cerr<<i<<": \n";
//			pstr.Print(pstr.root[i]);
			
			int x = pstr.GetPre(pstr.root[i], v);
			if(x == INF) {
				printf("%d\n", INCF);
				continue;
			}
			printf("%d\n", x); 
			continue;
		}
		if(op == 6) {
			pstr.root[i] = pstr.root[ver];
			
//			cerr<<pstr.tr[pstr.root[i]].val<<endl;
//			cerr<<i<<": \n";
//			pstr.Print(pstr.root[i]);
			
			int x = pstr.GetNext(pstr.root[i], v);
			if(x == INF) {
				printf("%d\n", INF);
				continue;
			}
			printf("%d\n", x); 
			continue;
		}
	}
	return 0;
}