2024.4.11 【虚怀若谷，戒骄戒躁。】
Thursday 三月初三
<theme = oi-“language”>
这个好东西叫pb_ds!!!
#include<bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;
堆
| 操作/数据结构 | 配对堆 | 二叉堆 | 左偏树 | 二项堆 | 斐波那契堆 |
|---|---|---|---|---|---|
| 代码 | pairing_heap_tag | binary_heap_tag | L_Tree | binomial_heap_tag | thin_heap_tag |
| insert(插入) | O(1) | O(logn) | O(logn) | O(1) | O(1) |
| find-min(找最小) | O(1) | O(1) | O(1) | O(logn) | O(1) |
| delete-min(删最小) | O(logn) | O(logn) | O(logn) | O(logn) | O(logn) |
| merge(合并) | O(1) | O(n) | O(logn) | O(logn) | O(1) |
| decrease-key(减小一个元素 ) | O(logn)~O(loglogn) | O(logn) | O(logn) | O(logn) | O(1) |
除配对堆和斐波那契堆之外都是支持可持久化的
不过还是建议使用这两个。。。
typedef pair<int, int > PII;
priority_queue<PII, greater<PII>, pairing_heap_tag> q;
priority_queue<PII, greater<PII>, pairing_heap_tag>::point_iterator its[N];
int dis[N];
vector<PII> g[N];
- push入堆
- pop出堆
- top堆顶
- empty判空
- size个数
- clear清空
平衡树
| rb_tree_tag | 红黑树 |
| splay_tree_tag | 旋转树 |
| ov_tree_tag | 有序向量树 |
基本操作方法
insert(x) //插入x
erase(x) //删除x
find_by_order(k) //求平衡树内排名为k的值是多少
order_of_key(x) //求x的排名
lower_bound(x) //求大于等于x的最小值
upper_bound(x) //求大于x的最小值
join(b) //合并
split(v, b) //分裂
食用
typedef pair<int, int> PII;
typedef tree<PII, null_type, less<PII>, rb_tree_tag, tree_order_statistics_node_update> Tree;
//这样用是因为pb_ds平衡树中不允许重复值的出现
哈希表
| cc_hash_table | 拉链法 |
| gp_hash_table | 探测法 |
食用
typedef gp_hash_table<string, int> hsmap;
显而易见，探测法会更快捷一点
哈希表是不支持 lower_bound 和 upper_bound 的
字典树
非常合理的食用方式
using Trie = __gnu_pbds::trie<string, null_type,
trie_string_access_traits<>,
pat_trie_tag,
trie_prefix_search_node_update>;
trie.insert(str);
trie.erase(str);
trie.join(another_trie);
// 遍历某一个前缀的所有字符串
pair<Trie::iterator, Trie::iterator> range = trie.prefix_range(prefix);
for(auto it = range.first; it != range.second; ++it)
cout << *it << endl;