pbds库
内容参考：比STL还STL？——平板电视
实测CF上需要开C++23才能通过编译
文章目录
- 头文件
- hash 哈希表
- tree 平衡树
- trie 字典树
- priority_queue 优先队列
头文件
万能
#include<bits/extc++.h>
using namespace __gnu_pbds;
分类
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>//用tree
#include<ext/pb_ds/hash_policy.hpp>//用hash
#include<ext/pb_ds/trie_policy.hpp>//用trie
#include<ext/pb_ds/priority_queue.hpp>//用priority_queue
using namespace __gnu_pbds;
hash 哈希表
定义
gp_hash_table<type, type> h;
用法和 map 一样，总时间复杂度 O ( n ) O(n) O(n)
tree 平衡树
定义
tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> tr;
其中 PII 表示存储类型，less<PII> 表示从小到大排序，tree_order_statistics_node_update 表示更新方式
支持操作 复杂度均为 O ( l o g n ) O(logn) O(logn)
insert(make_pair(x, y))插入erase(make_pari(x, y))删除order_of_key(PII(x, y))求排名find_by_order(k)找第k小值，返回迭代器join(b)将 b 并入原平衡树，要保证两棵树类型一样，没有重复元素split(v, b)分裂，小于等于v的属于原平衡树，其余属于 blower_bound(x)返回第一个大于等于 x 的元素迭代器upper_bound(x)返回第一个大于 x 的元素迭代器
trie 字典树
略 直接用数组实现吧
priority_queue 优先队列
定义
priority_queue<int, greater<int>, pairing_help_tag> Q; //小根堆，大根堆写less<int>
支持操作和普通优先队列差不多，不同点：
join(b)合并两个优先队列modify(it, 6)修改元素
时间复杂度，push 和 join 都是 O ( 1 ) O(1) O(1) ，其余 O ( l o g n ) O(logn) O(logn)