头文件:

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;//命名空间

定义方式:

// 不可重集合定义
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, 
         tree_order_statistics_node_update>;

// 可重集合定义(使用pair区分相同元素)
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, 
         rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;

插入操作:

ordered_set s;
s.insert(1);
s.insert(3);
s.insert(5);

删除操作:

s.erase(s.lower_bound(3));  // 删除第一个等于3的元素

查询排名(严格小于):

int rank = s.order_of_key(4);  // 返回小于4的元素个数

按排名查询:

auto it = s.find_by_order(1);  // 获取第2小的元素
int value = *it;