pbds 正确打开方式
AzusaShirasu
·
·
个人记录
不要问我为什么明明是写给自己看的还写的这么正式，因为我记忆力很不好，而且同一堑我要吃好几次才能长一智。所以写的正式一点方便日后查看时不会一头雾水。
句子文法可能略显冗长。
引入
pbds 可以理解成是 C++ 拓展出的一些更加有用的模板容器。相信很多选手都会有一段时间苦于背诵各种常用的数据结构的模板代码，pbds 将会是一个替代的好选择。它的优点有：
- 常数、速度不慢（特别注意：在 O2 优化下才是如此，尽管大部分竞赛都开了 O2）；
- 拥有可扩展性（支持自定义更新函数等，见下）；
- 代码简短；
- 最重要的，CCF 明确允许了 pbds 的使用。
本文是一些笔者的使用经验，通过简单讲解结合例题示范，旨在比普通的 pbds 教程多介绍一些常用的使用技巧，帮助大家更好的熟悉并掌握 pbds 的使用，不单单止于会用。
介绍难度是大致递增的。
Hash Table
哈希表，用哈希值决定元素的存储，时间复杂度平摊是 O(n) 的。但是建议自行编写哈希函数来降低在 Codeforces 上面被卡出 WA 或 TLE 来的可能。
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
cc_hash_table<int,int> cc;//链表
gp_hash_table<int,int> gp;//开放寻址
一般推荐使用效率较高的开放寻址 gp_hash_table。哈希表的索引类型需要实现 hash 接口。
常用函数：
find(x)，寻找 x 元素并返回一个迭代器指针；erase(x)，清除 x 元素；[x]，像 map 一样获取 x 索引的键值。
P8357 「WHOI-1」Derives
经过推导使用整除分块来加速 dp（具体过程不放出了，因为重点是在 hash_table 的使用上而不是推导）。
这题的特殊性质使得用链表哈希表会更快一些（最慢测试点比开放寻址法快了约 500ms）。关键代码：
```cpp
cc_hash_table<ll,ll> gp;
cc_hash_table<ll,ll> pre;
ll dp(ll x){
auto at=gp.find(x);
if(at!=gp.end())return at->second;
ll ans=0x7fffffffffffffffll;
ll N=x-1,p;
for(ll L=1,R;L<=N;L=R+1){
R=N/(N/L);
ll cur=dp(L)+(N/L+1)*b+x*a;
if(cur<ans)ans=cur,p=L;
}
pre[x]=p;
return gp[x]=ans;
}
const int maxn=10000000+5;
ll path[maxn],loc;
int main(){
cin>>n>>a>>b;
gp[1]=0,dp(n);
int cur=n,v;
while(v=pre[cur])path[++loc]=v,cur=v;
wr(gp[n],' '),wr(loc);
for(int i=1;i<=loc;i++)wr(path[i],' ');
io::flush();
return 0;
}
```
## Rope
`rope` 类似于块状链表（一说可持久化平衡树，又一说可持久化数组），虽然这么说，实际上和 `vector` 用法其实差不太多。`rope` 的插入、删除都是 $O(\sqrt n)$ 复杂度的（一说 $O(\log n)$）。
- 头文件：`#include<ext/rope>`；
- 命名空间：`using namespace __gnu_cxx;`。
- 声明方式：`rope<Type>`。
常用函数：
- `push_back(x)` 在末尾添加一个 `x`，类似于 `vector`；
- `insert(pos,x)`，在 `pos` 位置**后面**添加 `x`。这里的 `pos` 是一个整数，这意味着摆脱迭代器指针了。
- `erase(pos,len)`，在 `pos` 位置后面删除 `len` 个元素，也就是把 $[pos,pos+len)$ 区间的元素删除，再把后面的元素前移；
- `copy(pos,len,str)`，把 `pos` 后面 `len` 个元素替换为 `str`；
- `substr(pos,len)`，获取 `pos` 位置后面的 `len` 个元素；
- `replace(pos,x)`，把第 `pos` 个元素换成 `x`；
- `[x]`，访问第 `x` 个元素。像数组一样。
### [P3369 【模板】普通平衡树 ](https://www.luogu.com.cn/problem/P3369)
让我们用这道模板题作为例题来引入。
使用 Treap、Splay 等平衡树都能很轻松地过这道题。现在有一种用 `vector` 实现的平衡树，基于 `lower_bound` 和 `upper_bound` 操作，代码很短，如下：
```cpp
vector<int> v;
inline void insert(int x){v.insert(upper_bound(v.begin(),v.end(),x),x);}
inline void remove(int x){v.erase(lower_bound(v.begin(),v.end(),x));}
inline int rank(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
inline int kth(int x){return v[x-1];}
inline int getpre(int x){return*(--lower_bound(v.begin(),v.end(),x));}
inline int getnxt(int x){return *(upper_bound(v.begin(),v.end(),x));}
```
可以认为这份代码的时间复杂度是 $O(\sqrt n)$ 的。
现在用 `rope` 来实现一个类似的平衡树。大部分代码是通用的：
```cpp
rope<int> v;
inline void insert(int x){v.insert(upper_bound(v.begin(),v.end(),x)-v.begin(),x);}
inline int rank(int x){return lower_bound(v.begin(),v.end(),x)-v.begin()+1;}
inline void remove(int x){v.erase(rank(x)-1,1);}//note -1
inline int kth(int x){return v[x-1];}
inline int getpre(int x){return*(--lower_bound(v.begin(),v.end(),x));}
inline int getnxt(int x){return *(upper_bound(v.begin(),v.end(),x));}
```
时间复杂度大约为 $O(n \log^2n)$，实际效果不是很好（比 `vector` 平衡树慢了大约 $4$ 倍）。不过没关系，下面就会介绍一种新的容器来替代。
### [P4008 [NOI2003] 文本编辑器](https://www.luogu.com.cn/problem/P4008)
本题要求实现随机插入、删除、访问。前两个操作是链表基本操作，尽管如此，还是需要用块状链表或平衡树来实现普通的链表难以支持的第三个操作“访问”。
这里用 pbds 的 `rope` 容器。
关键代码：
```cpp
rope<char> txt;
int loc;
inline char skipspc(){
char c;while((c=getchar())&&(isspace(c)));
return c;
}
inline char gcmd(){
char c,ret=skipspc();
while((c=getchar())&&(!isspace(c)));
return ret;
}
inline int gnum(){
int x=skipspc()^'0';char c;
while((c=getchar())&&(isdigit(c)))x=(x<<3)+(x<<1)+(c^'0');
return x;
}
inline char gc(){
char c;while((c=getchar())&&(c=='\r'||c=='\n'));
return c;
}
int main(){
int n=gnum();
while(n--){
char cmd=gcmd();
int k;
switch(cmd){
case 'M':k=gnum(),loc=k;break;
case 'I':k=gnum();for(int i=1;i<=k;i++)txt.insert(loc++,gc());loc-=k;break;
case 'D':k=gnum();txt.erase(loc,k);break;
case 'G':k=gnum();printf("%s\n",txt.substr(loc,k).c_str());break;
case 'P':loc--;break;
case 'N':loc++;break;
}
}
}
```
### [P3605 [USACO17JAN]Promotion Counting P](https://www.luogu.com.cn/problem/P3605)
本题的标准做法是 dfs + 树状数组逆序对。事实上也可以用 pbds 解决。
从叶节点往父节点合并。先把所有子节点合并，接着查询父节点在子节点中的排名即为该节点的答案，最后并入父节点。使用 dfs 可以很方便地解决。关键代码：
```cpp
rope<int> v[maxn];
int fa[maxn],n,val[maxn];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void addx(int id,int x){
v[id].insert(upper_bound(v[id].begin(),v[id].end(),x)-v[id].begin(),x);
}
inline int Rank(int id,int x){
return lower_bound(v[id].begin(),v[id].end(),x)-v[id].begin()+1;
}
inline void join(int x,int y){
x=find(x),y=find(y);
if(v[x].size()>v[y].size())swap(x,y);
for(auto a:v[x])addx(y,a);
fa[x]=y,v[x].clear();
}
int f[maxn],ans[maxn];
vector<int> nxt[maxn];
void sol(int x){
ans[x]=0;
if(nxt[x].size()){
for(auto a:nxt[x])sol(a);
for(int i=0;i<nxt[x].size()-1;i++){
int X=nxt[x][i],y=nxt[x][i+1];
join(X,y);
}
int id=find(nxt[x][0]);
join(x,id);
ans[x]=v[id].size()-Rank(id,val[x]);
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)cin>>val[i],fa[i]=i,addx(i,val[i]);
for(int i=2;i<=n;i++){
int v;cin>>v;nxt[v].push_back(i);
}
sol(1);
for(int i=1;i<=n;i++)printf("%d\n",ans[i]);
return 0;
}
```
这里所用的启发式合并的技巧优化的具体讲解在马上就要来的下一节：比 `set` 更加强大的 `tree` 里。
## Tree
相比于 STL 里的 `set`，`tree` 有用的功能更多，它把那些因过度封装而被舍弃掉的实用功能，比如查询 $k$ 小值，给重新实现了出来。时间复杂度是 $O(\log n)$ 级别的。
- 头文件（有两个）：
```cpp
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
```
- 命名空间：`using namespace __gnu_pbds;`。
- 声明方式：
```cpp
tree<Type,Type,cmp,rb_tree_tag,tree_order_statistics_node_update> tr;
```
这里的 `cmp` 是一个用来比较元素大小的函数。如果觉得麻烦可以用 `less`、`less_equal`、`greater`、`greater_equal` 等代替，但是它们分别需要重载 `<`、`<=`、`>`、`>=` 运算符。
建议使用经测试性价比最高的 `rb_tree_tag` 的红黑树 tag。其他的 `tag` 可以自行查询手册或 Oi-Wiki 等帮助网站。
`tree_order_statistics_node_update` 是仿函数，功能类似于 `pushup`（或者叫做 `update` ），即通过子节点来计算父节点的信息。可以自己实现，但是比较麻烦（需要背的模板代码多），此处便不再列出详细写法。
常用函数：
- `insert(x)`，插入 `x`；
- `erase(x)`，删除 `x`。这里的 `x` 不是迭代器指针，它就是元素，或者说是我们维护的值；
- `find_by_order(x)`，查询第 `x` 小的元素，这里 `x` 从 $0$ 开始。返回的是一个迭代器，需要用取址运算符 `*` 来获取值；
- `order_of_key(x)`，查询 `x` 元素的排名，同样从 $0$ 开始；
- `join(tr)`，把树 `tr` 给合并到树中。这里的 `tr` 必须是同一类型的 `tree`，**两棵树的取值范围不能有交集，否则会 RE**（详细见下）。如果合并成功了，**`tr` 会被清空**；
- `split(x,tr)`，分裂树，把小于等于 `x` 的节点保留，其余的放到 `tr` 中；
- `lower_bound(x)`，返回大于等于 `x` 元素的迭代器；
- `upper_bound(x)`，返回严格大于 `x` 元素的迭代器。
`tree` 不允许元素有重复的问题相对解决：使用一个包含附加字段“特征值”的 `struct`，比如（这里用 `rand()` 生成特征值，最好换一个生成方式）：
```cpp
struct Num{
int v,id;
Num(){}
Num(int _v){v=_v,id=rand();}// <- Here
bool operator<(const Num&n)const{
return v!=n.v?v<n.v:id<n.id;
}
};
```
树的取值范围**不能有交集**，不仅仅是元素不允许重复。看如下代码，`a` 和 `b` 是两个 `tree`：
```cpp
a.insert(1),a.insert(2),a.insert(4);
b.insert(5);
a.join(b); // Ok
```
如果我们添加一个 `3` 到 `b` 中：
```cpp
a.insert(1),a.insert(2),a.insert(4);
b.insert(5);b.insert(3);
a.join(b); // Error
```
会抛出一个 `join_error` 的异常。捕获当然是可以的，不过没意义，因为你没有成功合并两棵树。
### [P3224 [HNOI2012]永无乡](https://www.luogu.com.cn/problem/P4008)
合并、查询 $k$ 小值，很容易想到用可分裂与合并的平衡树。虽然 Splay 或者 FHQTreap 的码量都不大，但是我们仍然可以用 pbds 里面的 `tree` 来更简便地实现需要的操作。
这时我们碰到了上面的没办法合并两棵取值范围相交的树的问题。暴力枚举其中一棵树的结点并 `insert`？可以，但是时间复杂度堪忧。
```cpp
void jointree(int x,int y){
int fx=find(x),fy=find(y);//Union-set, see below
if(fx==fy)return;
for(auto a:tr[fx])tr[fy].insert(a);
tr[fx].clear();
fa[fx]=fy;
}
```
其实只要一行就可以解决这个问题：用**启发式合并**，即每次合并操作都只把大小较小的那棵树合并到较大的树中。可以证明每个节点最多移动 $\log n$ 次，可以保证时间复杂度在 $O(\log n)$：
```cpp
if(fx==fy)return;
if(tr[fx].size()>tr[fy].size())swap(fx,fy);//<- Here
for(auto a:tr[fx])tr[fy].insert(a);
```
用并查集维护连通块，对每个连通块建立一棵 `tree`，启发式合并之后直接查询即可。
```cpp
int fa[maxn],n;
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
struct dao{
int v,id;
bool operator<(const dao&d)const{
return v!=d.v?v>d.v:id<d.id;
}
};
dao ds[maxn];
typedef tree<dao,null_type,less<dao>,rb_tree_tag,tree_order_statistics_node_update> treap;
treap tr[maxn];
void jointree(int x,int y){
int fx=find(x),fy=find(y);
if(fx==fy)return;
if(tr[fx].size()>tr[fy].size())swap(fx,fy);
for(auto a:tr[fx])tr[fy].insert(a);
tr[fx].clear();
fa[fx]=fy;
}
int main(){
int m;cin>>n>>m;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++)cin>>ds[i].v,ds[i].id=i;
while(m--){
int x,y;cin>>x>>y,fa[find(x)]=find(y);
}
for(int i=1;i<=n;i++)tr[find(i)].insert(ds[i]);
int q;cin>>q;while(q--){
char c;int x,y;
cin>>c>>x>>y;
if(c=='B')jointree(x,y);
else {
x=find(x);
if(y>tr[x].size())puts("-1");
else printf("%d\n",(*tr[x].find_by_order(tr[x].size()-y)).id);
}
}
return 0;
}
```
## Priority Queue
pbds 中的优先队列是**可并堆**。它可以提供给我们标准 STL 中同名的 `priority_queue` 无法提供的合并操作。操作的平摊最坏时间复杂度是 $O(\log n)$ 的。
- 头文件：`#include<ext/pb_ds/priority_queue.hpp>`
- 命名空间：`using namespace __gnu_pbds;`
- 声明方式：较为完整的写法是
```cpp
__gnu_pbds::priority_queue<int,less<int>,binomial_heap_tag> pq;
```
也可以简短一些，使用
```cpp
__gnu_pbds::priority_queue<int> pq;
```
如果不显式加上 `__gnu_pbds::`，并且又使用了 `using namespace std;`，会产生编译错误。这里建议手动添加。
`binomial_heap_tag` 用来决定堆的类型，这是性价比最高的标签之一。其他的由于时间或空间上有所差池并不常用。若想了解可以参阅相关资料。
常用函数：
- `push(x)`，往堆中添加 `x` 元素，**返回一个指向该元素的迭代器**（之后会用到它）；
- `pop()`，弹出堆顶元素；
- `top()`，获取堆顶元素但不弹出；
- `join(q)`，将 `q` 与堆合并，注意 `q` 必须是同一类型的 `priority_queue`，其余无限制；
- `modify(pos,x)`，将 `pos` 处的值修改为 `x`，这里的 `pos` 为迭代器；
- `erase(pos)`，移除 `pos` 迭代器处的元素。
### [P1456 Monkey King](https://www.luogu.com.cn/problem/P1456)
有了 `priority_queue` 之后就近乎模板题了，直接模拟即可。关键代码：
```cpp
struct scr{
int val,id;
bool operator<(const scr&s)const{
return val!=s.val?val<s.val:id<s.id;
}
};
__gnu_pbds::priority_queue<scr> q[maxn];
int fa[maxn];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int n;
void sol(){
for(int i=1;i<=n;i++)fa[i]=i,q[i].clear();
for(int i=1;i<=n;i++){
int x;cin>>x;q[i].push((scr){x,i});
}
int m;cin>>m;while(m--){
int x,y;
cin>>x>>y;
x=find(x),y=find(y);
if(x==y){
puts("-1");
continue;
}
scr fx=q[x].top();q[x].pop();
scr fy=q[y].top();q[y].pop();
if(q[x].size()>q[y].size())swap(x,y);
q[y].join(q[x]),fa[x]=y;
q[y].push((scr){fx.val>>1,fx.id});
q[y].push((scr){fy.val>>1,fy.id});
cout<<q[y].top().val<<endl;
}
}
```
然而，有些时候还需要动态修改堆中的元素，只用一个 `modify` 函数难以满足要求，所以需要维护一些额外的信息。
`push` 函数返回的迭代器是直接访问某个元素的少数方式之一，使用方式如下：
```cpp
typedef __gnu_pbds::priority_queue<int>::point_iterator addri;
addri addr=q.push(2);
q.modify(addr,1);// Now 2 will be modified to 1
```
如果不及时对这个返回的迭代器进行保存，那么你可能永远也访问不到它了。因此，在 `push` 元素的时候应当及时保存下来返回的迭代器。如果元素类型为值域不大的整数，开一个迭代器类型的数组就可以了；更通用的办法是使用 STL 的 `map` 或者 `gp_hash_map`：
```cpp
typedef __gnu_pbds::priority_queue<int>::point_iterator addri;
gp_hash_table<int,addri> qref;
```
**注意**：这样一来，两个堆合并就不能使用 `join` 函数了，我们必须手动将一个堆的元素合并到另一个堆中，才能获得这些元素的新的迭代器以便访问。如下是把 `p` 合并到 `q` 中的代码：
```cpp
for(auto x:p)qref[x]=q.push(x);
p.clear();
```
用**按秩合并**的思想可以降低可能的时间开销。
另外，上面的示例代码**未支持重复元素的迭代器保存**，使用 `struct` 或者 `pair<int,int>` 等技巧就能解决，这里不再给出代码。
### [P3273 [SCOI2011]棘手的操作](https://www.luogu.com.cn/problem/P3273)
题意：有加边操作，要求支持单点增加、连通块增加、全局增加和询问单点最值、连通最值、全局最值。
不难想到使用可并堆来执行操作，需要两个可并堆：一个维护各个连通块、一个维护全局。连通块增加可用一个数组 `add` 来
打标记，计算 / 询问时当场统计影响。接着使用保存迭代器的技巧来实现动态修改元素。
关键代码：
```cpp
struct node{
int val,id;
node(){}
node(int _val,int _id){val=_val,id=_id;}
bool operator<(const node&n)const{
return val!=n.val?val<n.val:id<n.id;
}
};
__gnu_pbds::priority_queue<node> blc[maxn];
__gnu_pbds::priority_queue<int> q;
typedef __gnu_pbds::priority_queue<node>::point_iterator addr;
gp_hash_table<int,addr> valref;
typedef __gnu_pbds::priority_queue<int>::point_iterator addri;
gp_hash_table<int,addri> qref;
int fa[maxn],val[maxn],add[maxn],n;
int alladd;
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
void merge(int x,int y){
x=find(x),y=find(y);
if(x==y)return;
if(blc[x].size()>blc[y].size())swap(x,y);
for(auto a:blc[x]){
val[a.id]=a.val+add[x]-add[y];
valref[a.id]=blc[y].push(node(val[a.id],a.id));
}
blc[x].clear(),fa[x]=y;
q.erase(qref[x]),q.modify(qref[y],blc[y].top().val+add[y]);
}
inline void A1(int x,int y){
int f=find(x);
val[x]+=y,blc[f].modify(valref[x],node(val[x],x));
q.modify(qref[f],blc[f].top().val+add[f]);
}
inline void A2(int x,int y){
int f=find(x);
add[f]+=y,q.modify(qref[f],blc[f].top().val+add[f]);
}
inline void A3(int x){
alladd+=x;
}
inline void F1(int x){
int f=find(x);
cout<<val[x]+add[f]+alladd<<endl;
}
inline void F2(int x){
int f=find(x);
cout<<blc[f].top().val+add[f]+alladd<<endl;
}
inline void F3(){
cout<<q.top()+alladd<<endl;
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)fa[i]=i;
for(int i=1;i<=n;i++)cin>>val[i],valref[i]=blc[i].push(node(val[i],i)),qref[i]=q.push(val[i]);
//省略部分代码
return 0;
}
```
### [P1110 [ZJOI2007] 报表统计](https://www.luogu.com.cn/problem/solution/P1110)
本题插入的数据呈链表式。
- `MIN_SORT_GAP`，全局最小差值显然不会增加，用一个变量维护即可；每插入一个数，对最小差值有贡献的是它的前继与后继，因此用一个平衡树保存。
- `MIN_GAP` 操作的步骤：使用一个堆来维护。
- `INSERT x` 操作的步骤：
- - 把当前链表的尾部与**下一个链表头部**的差值从堆中**删除**；
- - 将 `x` 与**当前链表尾部**、**下一个链表头部**的差值分别插入堆中；
- - 插入 `x`。
注意边界（即没有下一个链表的情况）特判。这时出现一个问题：堆的 `erase` 函数需要的是迭代器指针。这不难解决：用 `hash_table` 保存等技巧。这里采用了一个办法：另外开一些链表，当 `INSERT x` 的时候，把对应的指针插入到这些新链表中。具体可见代码：
```cpp
int n,m;
int val[maxn];
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> treap;
treap tr;
__gnu_pbds::priority_queue<int,greater<int>,binomial_heap_tag> pq;
typedef __gnu_pbds::priority_queue<int,greater<int>,binomial_heap_tag>::point_iterator pit;
vector<int> bc[maxn];
vector<pit> it[maxn];
int ming=0x7fffffff;
void tri(int x){
if(tr.find(x)!=tr.end())ming=0;
else {
tr.insert(x);
int r=tr.order_of_key(x);
ming=min(ming,min(abs(x-*tr.find_by_order(r-1)),abs(x-*tr.find_by_order(r+1))));
}
}
void add_val(int id,int x){
tri(x);
if(id<n)if(it[id].size()){
pq.erase(it[id][it[id].size()-1]);
it[id].pop_back();
}
it[id].push_back(pq.push(abs(bc[id][bc[id].size()-1]-x)));
if(id<n){
int c=abs(x-val[id+1]);
it[id].push_back(pq.push(c));
}
bc[id].push_back(x);
}
int main(){
cin>>n>>m;
tr.insert(-0x3f3f3f3f),tr.insert(0x3f3f3f3f);
for(int i=1;i<=n;i++)cin>>val[i],bc[i].push_back(val[i]),tri(val[i]);
for(int i=2;i<=n;i++)it[i].push_back(pq.push(abs(val[i]-val[i-1])));
// 省略部分代码
}
```