平衡树

参考资料

• 二叉搜索树 & 平衡树 - OI Wiki

pb_ds

tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> T;

例题

洛谷 P3369 【模板】普通平衡树

洛谷 P3369 【模板】普通平衡树

你需要写一种数据结构，来维护一些数，其中需要提供以下操作：

1. 插入一个数 $x$。
2. 删除一个数 $x$（若有多个相同的数，应只删除一个）。
3. 定义排名为比当前数小的数的个数 $+1$。查询 $x$ 的排名。
4. 查询数据结构中排名为 $x$ 的数。
5. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。
6. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。

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

tree<pair<int,int>,null_type,less<pair<int,int>>,rb_tree_tag,tree_order_statistics_node_update> T;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	int cnt=0;
	while(n--)
	{
		int op,x;
		cin>>op>>x;
		if(op==1)T.insert({x,++cnt});
		else if(op==2)T.erase(T.lower_bound({x,0}));
		else if(op==3)cout<<T.order_of_key({x,0})+1<<'\n';
		else if(op==4)cout<<T.find_by_order(x-1)->first<<'\n';
		else if(op==5)cout<<prev(T.lower_bound({x,0}))->first<<'\n';
		else if(op==6)cout<<T.lower_bound({x+1,0})->first<<'\n';
	}
	return 0;
}