要包 AC

#include <bits/stdc++.h>
using namespace std;
struct Treap 
{
	int val;
	int sz;
	int p;
	Treap* ch[2];
	void init(int v)
	{
		val = v, sz = 1, p = rand();
		ch[0] = ch[1] = NULL;
	}
};
Treap* t = NULL;
void renew(Treap* &root)
{
	root->sz = 1;
	if(root->ch[0] != NULL) root->sz += root->ch[0]->sz;
	if(root->ch[1] != NULL) root->sz += root->ch[1]->sz;
}
void split(Treap* root, int k, Treap* &x, Treap* &y)
{
	if(root == NULL)
	{
		x = y = NULL;
		return ;
	}
	if(root->val <= k)
	{
		x = root;
		split(x->ch[1], k, x->ch[1], y);
		renew(x);
	}
	else
	{
		y = root;
		split(y->ch[0], k, x, y->ch[0]);
		renew(y);
	}
}
Treap* merge(Treap* x, Treap* y)
{
	if(x == NULL) return y;
	if(y == NULL) return x;
	if(x->p < y->p)
	{
		x->ch[1] = merge(x->ch[1], y);
		renew(x);
		return x;
	}
	else
	{
		y->ch[0] = merge(x, y->ch[0]);
		renew(y);
		return y;
	}
}
void insert(int val)
{
	Treap* node = new Treap;
	node->init(val);
	Treap* x;
	Treap* y;
	split(t, val, x, y);
	t = merge(merge(x, node), y);
}
void print(Treap* root)
{
	if(root == NULL) return ;
	print(root->ch[0]);
	cout << root->val << " ";
	print(root->ch[1]);
}
void del(Treap* &root)
{
	if(root == NULL) return ;
	del(root->ch[0]);
	del(root->ch[1]);
	delete root;
}
void erase(int x)
{
	Treap* a;
	Treap* b;
	Treap* c;
	Treap* d;
	split(t, x-1, a, b);
	split(b, x, c, d);
	delete c;
	t = merge(a, d);
}
int ranking(Treap* root, int x)
{
	if(root == NULL) return 0;
	if(root->val < x)
		return (root->ch[0]->sz)+1+ranking(root->ch[1], x);
	else
		return ranking(root->ch[0], x);
}
int query(Treap* root, int x)
{
	int ls = 0;
	if(root->ch[0] != NULL) ls = root->ch[0]->sz;
	if(x <= ls)
		return query(root->ch[0], x);
	else if(x == ls+1)
		return root->val;
	else
		return query(root->ch[1], x-ls-1);
}
int pre(int x)
{
	Treap* tmp = t;
	int Max = -1000000009;
	while(tmp != NULL)
	{
		if(tmp->val < x)
		{
			Max = max(Max, tmp->val);
			tmp = tmp->ch[1];
		}
		else
			tmp = tmp->ch[0];
	}
	return Max;
}
int suc(int x)
{
	Treap* tmp = t;
	int Min = 1000000009;
	while(tmp != NULL)
	{
		if(tmp->val > x)
		{
			Min = min(Min, tmp->val);
			tmp = tmp->ch[0];
		}
		else
			tmp = tmp->ch[1];
	}
	return Min;
}
signed main()
{
	srand(time(0));
	int n;
	cin >> n;
	for(int i=1;i<=n;i++)
	{
		int op, x;
		cin >> op >> x;
		if(op == 1)
			insert(x);
		else if(op == 2)
			erase(x);
		else if(op == 3)
			cout << ranking(t, x) << "\n";
		else if(op == 4)
			cout << query(t, x) << "\n";
		else if(op == 5)
			cout << pre(x) << "\n";
		else
			cout << suc(x) << "\n";
	}
//	print(t);
	del(t);
	return 0;
}

记录