明天就是一轮省选了啊。。这可能是退役前的最后一篇博文了吧(如果心情不好怕是连游记都会咕)
众周所知stl中有一个依靠红黑树实现的nb数据结构-std::set
但是这玩意儿没有维护siz域，也就是不能做类似于询问rank(i)(查询\(i\)的排名)和kth(i)(查询排名为\(i\)的数)
但是stl中还有一个更nb的东西-pb_ds中的平衡树
定义的话首先要引用
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>然后
__gnu_pbds::tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> s;就可以啦
可以使用：
s.order_of_key(i)来得到值为\(i\)的数的排名
*s.find_by_order(i)来得到排名为\(i\)的数
复杂度比手写的慢很多，但大概还是log级别，所以考场上如果条件允许的话说不定可以救你一命~
原文：https://www.cnblogs.com/zwfymqz/p/10660141.html