treap平衡树模板

#include 
using namespace std;
const double pi = acos(-1);
const double eps=1e-7;
const int base=132;
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
#define x first
#define y second
#define int long long
#define lb long double
#define pb push_back
#define endl '\n'//交互题删掉此 
#define all(v) (v).begin(),(v).end()
#define PII pair<int,int>
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dwn(i,n,x) for(int i=n;i>=x;i--)
#define ll_INF 0x7f7f7f7f7f7f7f7f
#define INF 0x3f3f3f3f
#define debug(x) cerr << #x << ": " << x << endl
#define io ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
int Mod(int a,int mod){return (a%mod+mod)%mod;}
int lowbit(int x){return x&-x;}//最低位1及其后面的0构成的数值
int qmi(int a, int k, int p){int res = 1 % p;while (k){if (k & 1) res = Mod(res * a , p);a = Mod(a * a , p);k >>= 1;}return res;}
int inv(int a,int mod){return qmi(a,mod-2,mod);}
int n;
const int N=100010;
struct node
{
	int l,r;//左右孩子 
	int key,val;//搜索树中的编号，堆中的编号 
	int cnt,sz;//相同元素的个数，该结点为根结点的子树的节点树 
}tr[N];
int root,idx;
void pushup(int p)//向上更新 
{
	tr[p].sz=tr[tr[p].l].sz+tr[tr[p].r].sz+tr[p].cnt;
}
int get_node(int key)
{
	tr[++idx].key=key;
	tr[idx].val=rand();
	tr[idx].cnt=tr[idx].sz=1;
	return idx;
}
void zig(int &p)
{
	int q=tr[p].l;
	tr[p].l=tr[q].r,tr[q].r=p,p=q;
	pushup(tr[p].r),pushup(p);
}
void zag(int &p)
{
	int q=tr[p].r;
	tr[p].r=tr[q].l,tr[q].l=p,p=q;
	pushup(tr[p].l),pushup(p);
}
void build()
{
	get_node(-INF),get_node(INF);
	root=1,tr[1].r=2;
	pushup(root);
	if(tr[1].val<tr[2].val)zag(root);
}
void insert(int &p,int key)
{
	if(!p)p=get_node(key);
	else if(tr[p].key==key)tr[p].cnt++;
	else if(tr[p].key>key)
	{
		insert(tr[p].l,key);
		if(tr[tr[p].l].val>tr[p].val)zig(p);
	}
	else
	{
		insert(tr[p].r,key);
		if(tr[tr[p].r].val>tr[p].val)zag(p);
	}
	pushup(p);
}
void remove(int &p,int key)
{
	if(!p)return;
	if(tr[p].key==key)
	{
		if(tr[p].cnt>1)tr[p].cnt--;
		else if(tr[p].l||tr[p].r)
		{
			if(!tr[p].r||tr[tr[p].l].val>tr[tr[p].r].val)
			{
				zig(p);
				remove(tr[p].r,key);
			}
			else
			{
				zag(p);
				remove(tr[p].l,key);
			}
		}
		else p=0;
	}
	else if(tr[p].key>key)remove(tr[p].l,key);
	else remove(tr[p].r,key);
	pushup(p);
}
int get_rank_by_key(int p,int key)//通过数值找排名 
{
	if(!p)return 0;
	if(tr[p].key==key)return tr[tr[p].l].sz+1;
	if(tr[p].key>key)return get_rank_by_key(tr[p].l,key);
	return tr[tr[p].l].sz+tr[p].cnt+get_rank_by_key(tr[p].r,key);
}
int get_key_by_rank(int p,int rank)//通过排名找数值 
{
	if(!p)return INF;
	if(tr[tr[p].l].sz>=rank)return get_key_by_rank(tr[p].l, rank);
	if(tr[tr[p].l].sz+tr[p].cnt>=rank)return tr[p].key;
	return get_key_by_rank(tr[p].r,rank-tr[tr[p].l].sz-tr[p].cnt);
}
int get_prev(int p,int key)//找到严格小于key的最大数
{
	if(!p)return -INF;
	if(tr[p].key>=key)return get_prev(tr[p].l,key);
	return max(tr[p].key,get_prev(tr[p].r,key));
}
int get_next(int p,int key)//找到严格大于key的最小数
{
	if(!p)return INF;
	if(tr[p].key<=key)return get_next(tr[p].r,key);
	return min(tr[p].key,get_next(tr[p].l,key));
}
void solve()
{
	build();
	cin>>n;
	while(n--)
	{
		int op,x;
		cin>>op>>x;
		if(op==1)insert(root,x);
		else if(op==2)remove(root,x);
		else if(op==3)cout<<get_rank_by_key(root,x)-1<<endl;
		else if(op==4)cout<<get_key_by_rank(root,x+1)<<endl;
		else if(op==5)cout<<get_prev(root,x)<<endl;
		else cout<<get_next(root,x)<<endl;
	}
}
signed main()
{
    io;
    int _;_=1;
    //cin>>_;
    while(_--)solve();
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155