C++|C++ pbds 库平衡树（tree） C++pbds库平衡树（tree）

头文件

#include #include //或者直接用 #include

命名空间

using namespace __gnu_pbds;

定义

tree, rb_tree_tag, tree_order_statistics_node_update> T; //这个东西有一点点长 //第一个参数是数据类型 //第二个要填null_type，低版本编译器填null_mapped_type //第三个填比较函数 std::greater<> or std::less<> or cmp //第四个填树的类型，有rb_tree_tag红黑树和splay_tree_tag //第五个是为了支持查询第k大和排名的一个参数 //tree_order_statistics_node_update

使用这个东西和\(set\)一样不支持重复元素，所以一般用\(double\)，或者自定义结构体变量或者用\(pair\)都是可以的，只要记住千万不要插入重复元素就好了。
【C++|C++ pbds 库平衡树（tree）】洛谷模板：普通平衡树

#include #include #include using namespace std; using namespace __gnu_pbds; tree, rb_tree_tag, tree_order_statistics_node_update> T; int main() { //freopen("3369.in", "r", stdin); //freopen("3369.out", "w", stdout); int q, opt, x; scanf("%d", &q); for (int i = 1; i <= q; ++ i) { scanf("%d%d", &opt, &x); if(opt == 1) T.insert(x + i * 1e-6); //插入一个数 if(opt == 2) T.erase(T.lower_bound(x)); //删除一个数 if(opt == 3) printf("%d\n", (int)T.order_of_key(x) + 1); //查询一个数的排名 if(opt == 4) printf("%d\n", (int)*T.find_by_order(x - 1)); //查询第k小的数返回的是一个迭代器这里k是从0开始算的，意思是最小的数是第0小的 if(opt == 5) printf("%d\n", (int)round(*(-- T.lower_bound(x)))); //查询一个数的前驱 if(opt == 6) printf("%d\n", (int)round(*T.lower_bound(x + 1))); //查询一个数的后继 }return 0; }

这个东西在比赛中是可以用的，所以如果嫌打平衡树太麻烦就可以直接用啦。