猎奇Treap58pts~65pts随机分数 玄关求条

#include <bits/stdc++.h>
#define rnd() rand()

using namespace std;

const int N = 110000, inf = 1 << 30;
int q, rt, tot;
struct Info {
	int l, r, rd, sz, cnt, val, dat;
} a[N];
struct Treap {
	#define l(p) a[p].l
	#define r(p) a[p].r
	
	inline int New(int val) {
		a[++tot].val = val;
		a[tot].dat = rnd();
		a[tot].sz = a[tot].cnt = 1;
		return tot;
	}
	
	inline void update(int &p) {
		a[p].sz = a[l(p)].sz + a[r(p)].sz + a[p].cnt;
	}
	
	inline void zig(int &p) {
		int q = l(p);
		l(p) = r(q), r(q) = p;
		p = q;
		update(r(p)), update(p);
	}
	
	inline void zag(int &p) {
		int q = r(p);
		r(p) = l(q), l(q) = p;
		p = q;
		update(l(p)), update(p);
	}
	
	inline void build() {
		rt = New(-inf), r(rt) = New(inf);
		update(rt);
	}
	
	inline void insert(int &p, int val) {
		if (p == 0) 
			return p = New(val), void();
		if (a[p].val == val)
			a[p].cnt++;
		else if (val < a[p].val) {
			insert(l(p), val);
			if (a[l(p)].dat > a[p].dat)
				zig(p);
		} else {
			insert(r(p), val);
			if (a[r(p)].dat > a[p].dat)
				zag(p);
		}
		update(p);
	}
	
	inline void remove(int &p, int val) {
		if (p == 0)
			return;
		if (val == a[p].val) {
			if (a[p].cnt) {
				if (!(--a[p].cnt))
					remove(p, val);
			} else if (a[p].l || a[p].r) {
				if (!a[p].r || a[l(p)].dat > a[r(p)].dat)
					zig(p), remove(r(p), val);
				else
					zag(p), remove(l(p), val);
			} else
				p = 0;
		} else if (val < a[p].val)
			remove(l(p), val);
		else
			remove(r(p), val);
		update(p);
	}
	
	inline int Rank(int &p, int val) {
		if (p == 0)
			return 1;
		if (val == a[p].val)
			return a[l(p)].sz + 1;
		if (val < a[p].val)
			return Rank(l(p), val);
		return Rank(r(p), val) + a[l(p)].sz + a[p].cnt;
	}
	
	inline int Val(int &p, int k) {
		if (p == 0)
			return inf;
		if (k <= a[l(p)].sz)
			return Val(l(p), k);
		 if (k <= a[l(p)].sz + a[p].cnt)
		 	return a[p].val;
		return Val(r(p), k - a[l(p)].sz - a[p].cnt);
	}
	
	inline int Pre(int val) {
		int ans = 1;
		int p = rt;
		while (p) {
			if (val == a[p].val) {
				p = l(p);
				while (r(p))
					p = r(p);
				ans = p;
			} 
			if (a[p].val < val && a[p].val > a[ans].val)
				ans = p;
			if (val < a[p].val)
				p = l(p);
			else
				p = r(p);
		}
		return a[ans].val;
	}
	
	inline int Next(int val) {
		int ans = 2;
		int p = rt;
		while (p) {
			if (val == a[p].val) {
				p = r(p);
				while (l(p))
					p = l(p);
				ans = p;
			}
			if (a[p].val > val && a[p].val < a[ans].val)
				ans = p;
			if (val < a[p].val)
				p = l(p);
			else
				p = r(p);
		}
		return a[ans].val;
	}
	
	inline int query(int op, int val) {
		if (op == 3)
			return Rank(rt, val) - 1;
		else if (op == 4)
			return Val(rt, val + 1);
		else if (op == 5)
			return Pre(val);
		else
			return Next(val);
	}
} tp;

int main() {
	srand(time(0));
	tp.build();
	scanf("%d", &q);
	for (; q--; ) {
		int op, x;
		scanf("%d%d", &op, &x);
		if (op == 1)
			tp.insert(rt, x);
		else if (op == 2)
			tp.remove(rt, x);
		else 	
			printf("%d\n", tp.query(op, x));
	}
	return 0;
}