感谢 原大连市第二十四中学---于纪平 同学
Eromanga_Sensei——Izumi Sagiri
- 在百度上还没有看到PB_DS的相关整理，所以自己整理了一份综合性的、附带注释和可选择项的PB_DS的“帮助文档”，在自己若干次比赛中测试下来可用，PC^2环境下完美运行。
- PB_DS拓展库可以快速的实现一些复杂算法，比如红黑树，AVL等等，虽然可操作性肯定不如手写树，能实现的功能也比较有限，但是可以在赛场上对拍子，或者对于那些高级数据结构掌握不太好的人是一种福利，水过不是梦~~~
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class Node_CItr, class Node_Itr, class Cmp_Fn, class _Alloc> struct my_node_update {
virtual Node_CItr node_begin() const = 0;
virtual Node_CItr node_end() const = 0;
typedef int metadata_type;
inline void operator()(Node_Itr it, Node_CItr end_it) {
Node_Itr l = it.get_l_child(), r = it.get_r_child();
int left = 0, right = 0;
if (l != end_it) left = l.get_metadata();
if (r != end_it) right = r.get_metadata();
const_cast<metadata_type &>(it.get_metadata()) = left + right + (*it)->second;
}
inline int prefix_sum(int x) {
int ans = 0;
Node_CItr it = node_begin();
while (it != node_end()) {
Node_CItr l = it.get_l_child(), r = it.get_r_child();
if (Cmp_Fn()(x, (*it)->first)) {
it = l;
} else {
ans += (*it)->second;
if (l != node_end()) {
ans += l.get_metadata();
}
it = r;
}
}
return ans;
}
inline int interval_sum(int l, int r) {
return prefix_sum(r) - prefix_sum(l - 1);
}
inline int order_of_key(int x) {
int ans = 0;
Node_CItr it = node_begin();
while (it != node_end()) {
Node_CItr l = it.get_l_child();
Node_CItr r = it.get_r_child();
if (Cmp_Fn()(x, **it)) {
it = l;
} else {
ans++;
if (l != node_end()) {
ans += l.get_metadata();
}
it = r;
}
}
return ans;
}
};
int main() {
//pb_ds中priority_queue下相关操作
__gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> p;
//__gnu_pbds::priority_queue<Value_Type, greater/less<Value_Type>, pairing_heap_tag(配对堆)/binary_heap_tag(二叉堆)/binomial_heap_tag(二项堆)/rc_binomial_heap_tag(冗余计数二项式堆)/thin_heap_tag(斐波那契堆)> Name;
//pairing_heap_tag: push 和 join 为O(1) 其余均摊为O(log n)
//binary_heap_tag: 只支持 push 和 pop 均为均摊O(log n)
//binomial_heap_tag: push 为均摊O(1) 其余为O(log n)
//rc_binomial_heap_tag: push 为O(1) 其余为O(log n)
//thin_heap_tag: push 为O(1) 不支持 join 其余为O(log n) 如果只有 increase_key 那么 modify 为均摊O(1)
//其他默认操作: push pop modify erase join
__gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag>::point_iterator it = p.push(0);
p.push(1), p.push(2);
//modify 修改 it 处的值为 3
p.modify(it, 3);
//assert 计算表达式是否正确 错误则会退出程序
assert(p.top() == 3);
//删除 it 处的值
p.erase(it);
assert(p.top() == 2);
//join 为合并两个堆,将q合并入p中，清空q
__gnu_pbds::priority_queue<int, less<int>, pairing_heap_tag> q;
p.join(q);
//pb_ds中tree下相关操作
__gnu_pbds::tree <int, int, greater<int>, rb_tree_tag, tree_order_statistics_node_update> Tree1; //类似map
__gnu_pbds::tree <int, null_type, greater<int>, rb_tree_tag, tree_order_statistics_node_update> Tree2; //类似set
//__gnu_pbds::tree <Value_Key, Type/null_Type/null_mapped_type, greater/less<Type>, rb_tree_tag(红黑树)/splay_tree_tag(Spaly树)/ov_tree_tag(有序向量树), null_tree_node_update/tree_order_statistics_node_update>
__gnu_pbds::tree <int, int, greater<int>, rb_tree_tag, tree_order_statistics_node_update>::iterator it2;
//成员函数iterator find_by_order(size_type order) 找到第order+1小的元素的迭代器 如果order太大会返回end()
it2 = Tree1.find_by_order(1);
//成员函数size_type order_of_key(const_key_reference r_key) 这个tree中有多少个比r_key小的元素
int t1 = Tree1.order_of_key(1);
//join(tree &other) 把other的所有元素移动到*this中(要求oher和*this的值域不能相交)
__gnu_pbds::tree <int, int, greater<int>, rb_tree_tag, tree_order_statistics_node_update> Tree11;
Tree1.join(Tree11);
//split(const_key_reference r_key, tree &other) 清空other 然后把*this当中所有大于r_key的元素移至other
Tree1.split(1, Tree11);
//使用自定义node_update 查询子段和 查询前项和
__gnu_pbds::tree <int, int, less<int>, rb_tree_tag, my_node_update> T;
__gnu_pbds::tree <int, int, less<int>, rb_tree_tag, my_node_update>::iterator it3;
T[2] = 100, T[3] = 1000, T[4] = 10000, T.insert(make_pair(1, 1));
cout << T.interval_sum(3, 4) << " " << T.prefix_sum(3) << endl;//11000 1101
//iterator begin() end() find(const Key) lower_bound(const Key) upper_bound(const Key)//前驱后继
it3 = T.begin(), it3 = T.end(), it3 = T.find(2), it3 = T.lower_bound(2), it3 = T.upper_bound(2);
//int size()
int s = T.size();
//bool empty()
bool tmp = T.empty();
//void clear() erase(iterator) erase(const Key) insert(const pair<Key,T>)
T.erase(it3), T.erase(2), T.insert(make_pair(1, 1)), T.clear();
//pb_ds中hash_table 代替日常中使用的map
__gnu_pbds::cc_hash_table <int, int> h1; //拉链法
__gnu_pbds::gp_hash_table <int, int> h2; //查探法 理论速度更快
__gnu_pbds::gp_hash_table <int, int>::point_iterator it4;//与pb_ds优先队列的一样
//eg.
//int n, m, t;
//cin >> n >> m;
//while (n--) {
// cin >> t, h2[t] = 1;
//}
//while (m--) {
// cin >> t;
// if (h2[t] == 1) cout << "YES" << endl;
// else cout << h2[t] << endl;// 0
//}
//pb_ds中Trie下的相关操作
__gnu_pbds::trie <string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> Trie;
typedef __gnu_pbds::trie <string, null_type, trie_string_access_traits<>, pat_trie_tag, trie_prefix_search_node_update> pref_trie;
//void insert(string s) erase(string s) join(trie &b)
//eg.
//string x, cin >> x, x = x + "$";
//for (int i = 0; i < x.length(); i++) Trie.insert(x.substr(i)); //string:: substr(int start, int length) 从start开始 长度为length的子串
//string t, cin >> t;
//int n = 0;
//pair<pref_trie::iterator, pref_trie::iterator> range = Trie.prefix_range(t);
//for (pref_trie::iterator it = range.first; it != range.second; it++) n++;
//cout << n;
//pair中第一个是起始迭代器，第二个是终止迭代器，遍历过去就可以找到所有字符串了。
//既然有了trie,我们就可以实现简单的后缀树：(如下,查找一个字符串在另一个字符串中出现了多少次)
return 0;
}
附加原PDF：下载链接
网友评论