前言
9月1日吸吸F发了个这个东西关于NOI系列活动中编程语言使用限制的补充说明，点进去一看，好啊！！能用下划线开头的东西了，于是就来学了pb_ds
什么是pb_ds
pb_ds全称 Policy based data structures 字面意思就是基于策略的数据结构（废话！）它里面有hash,tree,trie,priority_queue这四种数据结构。
其中hash的作用和map类似，有两种hash的实现方法cc_hash_table<int,bool> h; gp_hash_table<int,bool> h;其中cc开头为拉链法(collision-chaining)，gp(general-probing)开头为探测法(faster?)
为啥要用hash_table而不用map呢？因为map的总时间复杂度为 $O(nlogn)$ 而hash_table的总时间复杂度为 $O(n)$
pbds里面的tree都是平衡树，其中有rb_tree,splay_tree(mayb TLE),ov_tree(mayb TLE)
trie和priority_queue就是字面意思，但是pb_ds里的priority_queue比STL中的多几个操作
priority_queue包含 binary_heap, binomial_heap, pairing_heap, rc_binomial_heap, thin_heap 这几种类型
怎么用pb_ds
可以使用 bits/extc++.h 头文件，如果没有就加上
1
2
3
4
5
|
#include<ext/pb_ds/assoc_container.hpp>
#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>
|
除此以外还需要使用 __gnu_pbds 命名空间，然后就可以使用pb_ds了！
Hash
1
2
3
|
__gnu_pbds::cc_hash_table<Key, Mapped>
__gnu_pbds::gp_hash_table<Key, Mapped>
|
和map差不多，不多说了
Tree
1
|
__gnu_pbds::tree<Key, T>
|
1
2
3
4
5
6
7
|
template<typename Key, typename Mapped, typename Cmp_Fn = std::less<Key>,
typename Tag = rb_tree_tag,
template<typename Node_CItr, typename Node_Itr,
typename Cmp_Fn_, typename _Alloc_>
class Node_Update = null_node_update,
typename _Alloc = std::allocator<char> >
class tree
|
tag指树的类型，就是上面说到的三种树
显然这个Node_Update有点意思，默认值是空，库中也提供了非空的选项tree_order_statistics_node_update，这时tree就有了find_by_order和order_of_key两个函数。它真正nb在你可以自己写一个Node_Update来实现一些操作。
emm，说一下find_by_order和order_ok_key两个函数
iterator find_by_order(size_type order) 找第order+1小的元素的迭代器，若找不到返回end()
size_type order_of_key(const_key_reference r_key)询问树中有多少小于r_key的元素
tree和map的用法基本相同，操作有：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
begin()
end()
size()
empty()
clear()
find(const Key)
lower_bound(const Key)
upper_bound(const Key)
erase(tree::iterator)
erase(const Key)
insert(const pair<Key, T>)
operator[] (const Key)
join(tree &another)
spilt(const_key_reference r_key, tree &another)
|
如果不想用Set，把第二个参数改为null_type此时iterator指向的就不是一个pair了
join和spilt都是void类型的，join是吧another的所有元素合并到当前树中(*this)，如果值域有相交，则会抛出异常。spilt是把another清空并把当前树中所有大于r_key的元素移动到another中
普通平衡树的代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <bits/extc++.h>
#include <bits/stdc++.h>
#define For(i, l, r) for (int i = (l), i##end = (r); i <= i##end; ++i)
#define Fordown(i, r, l) for (int i = (r), i##end = (l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
template <typename LDXIN>
LDXIN read() {
LDXIN s = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch > '9') {
if (ch == '-') f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s * f;
}
tree<long long, null_type, less<long long>, rb_tree_tag,
tree_order_statistics_node_update>
tr;
int n, m;
long long k, ans;
int main() {
n = read<int>();
For(i, 1, n) {
int opt = read<int>();
k = read<long long>();
switch (opt) {
case 1:
tr.insert((k << 20) + i);
break;
case 2:
tr.erase(tr.lower_bound(k << 20));
break;
case 3:
printf("%d\n", tr.order_of_key(k << 20) + 1);
break;
case 4:
ans = *tr.find_by_order(k - 1), printf("%lld\n", ans >> 20);
break;
case 5:
ans = *--tr.lower_bound(k << 20), printf("%lld\n", ans >> 20);
break;
default:
ans = *tr.upper_bound((k << 20) + n), printf("%lld\n", ans >> 20);
break;
}
}
return 0;
}
|
自己写Node_Update
自带的tree_order_statistics_node_update统计的是子树的size
1
2
3
4
5
6
7
8
9
|
template<class Node_CItr,class Node_Itr,class Cmp_Fn,class _Alloc>
struct my_node_update
{
void operator()(Node_Itr it, Node_CItr end_it)
{
...
}
};
|
节点更新的tree都会保存一个metadata_type类型（指节点上记录的额外信息的类型）的变量。当我们修改这棵树的时候，会从叶子节点开始修改，并且每次都会调用operator()，我们来看一下这个函数的两个参数：
Node_Itr it为调用该函数的元素的迭代器，Node_CItr end_it表示空节点，Node_Itr有以下的操作：
1.get_l_child()，返回其左孩子的迭代器，没有则返回node_end；
2.get_r_child()，同get_l_child()；
3.get_metadata()，返回其在树中维护的数据；
4.**it可以获取it的信息。
更新子树大小的例子：
1
2
3
4
5
6
7
8
9
|
void operator()(Node_Itr it, Node_CItr end_it)
{
Node_Itr l=it.get_l_child();
Node_Itr 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<int&>(it.get_metadata())=left+right+1;
}
|
const_cast是去除const限定用的（虽然不能修改const变量的值，否则为UB），它的作用在于当我们调用了一个参数不是const的函数时，若要传进去的实际参数是const的，但是我们知道这个函数是不会对参数做修改时。我们就需要使用const_cast去除const限定，以便函数能够接受这个实际参数。
现在我们学会了更新，那么我们该如何自己写操作呢？node_update所有public方法都会在树中公开。如果我们在node_update中将它们声明为virtual，则可以访问基类中的所有virtual。所以，我们在类里添加以下内容：
1
2
|
virtual Node_CItr node_begin() const=0;
virtual Node_CItr node_end() const=0;
|
这样我们就能直接访问树了
Priority_queue
__gnu_pbds::priority_queue<T>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
/**
* A priority queue composed of one specific heap policy.
*
* @tparam _Tv Value type.
* @tparam Cmp_Fn Comparison functor.
* @tparam Tag Instantiating data structure type,
* see container_tag.
* @tparam _Alloc Allocator type.
*
* Base is dispatched at compile time via Tag, from the following
* choices: binary_heap_tag, binomial_heap_tag, pairing_heap_tag,
* rc_binomial_heap_tag, thin_heap_tag
*
* Base choices are: detail::binary_heap,(二叉堆) detail::binomial_heap（二顶堆）,
* detail::pairing_heap（配对堆）, detail::rc_binomial_heap,
* detail::thin_heap.
*/
template<typename _Tv,
typename Cmp_Fn = std::less<_Tv>,
typename Tag = pairing_heap_tag,
typename _Alloc = std::allocator<char> >
class priority_queue
|
Tag即为上面提到的几种堆的类型
_Alloc不bird它
基本操作：
1
2
3
4
5
6
|
size()
empty()
push(const T)
top()
pop()
clear()
|
其他操作（比STL多的）：
1
2
3
4
|
point_iterator push(const_reference)
void join(priority_queue &another)
void modify(point_iterator, const_reference)
void erase(point_iterator)
|
Example:
1
2
3
4
5
6
7
8
|
priority_queue<int> p;
priority_queue<int>::point_iterator it = p.push(0);
p.push(1);
p.push(2);
p.modify(it, 3);
assert(p.top() == 3);
p.erase(it);
assert(p.top() == 2);
|
join为把another合并到当前堆，并清空another
时间复杂度
- pairing_heap_tag push和join为 $O(1)$ 其他均摊 $O(nlogn)$
- binary_heap_tag 只支持push和pop，均摊 $O(nlogn)$
- binomical_heap_tag push均摊 $O(1)$ 其余 $O(nlogn)$
- rc_binomical_heap_tag push $O(1)$ 其余 $O(nlogn)$
- thin_heap_tag push $O(1)$ 不支持join 其他 $O(nlogn)$，若只有increase_key modify均摊 $O(1)$
Trie
最后
直接用pb_ds换掉set/map/priority_queue不会使程序变慢
Reference:
- WC2015营员交流C++的pb_ds库在OI中的应用
- 比STL还STL？——平板电视