浅谈pbds

科技

CCF在 $21$ 年出版的新规定中已经允许使用下划线库函数了，pbds 的合法性已经在noi系列赛事得到了承认

是这样的大家平时写代码是不是经常会用到 stl

但是这个玩意是不是一边一边嫌弃：set 明明是平衡树但是功能严重阉割，deque 空间时间都有毛病，priority_queue 不是可并堆...

烦死了，蠢B STL!!!!

有没有什么好的替代方案呢，假如说考场上不想写平衡树不想写可并堆（deque 很好手写那就手写得了）

现在介绍——pbds库

头文件与namespace

#include <bits/extc++.h>
using namespace __gnu_cxx;
using namespace __gnu_pbds;

背下来就可以了

priority_queue

是的，pbds 也有优先队列，所以为什么不把这玩意代替掉默认的那个呢

注意事项

• 依旧是 stl 同款傻子“反的”仿函数规则
• 声明要加 __gnu_pbds:: 防止和 stl 的冲突
• 跟STL中的声明不一样，STL中是第三个参数是仿函数类，而pbds中则是第二个参数是仿函数类，第三个参数是堆的类型

参数

定义的时候不需要加入 vector<T>

一共需要三个参数：

• 元素类型
• 仿函数类
• 堆的类型

其中仿函数可以用 greater<T>,less<T>，也可以手写一个自己的

例如：

struct myCmp{//按照b降序(小根)
    bool operator()(node x, node y){//此时要将y想象成 排在优先队列前面的元素
        return x.b < y.b;
    }
};

需要注意的是堆的类型，其实有很多种

• pairing_heap_tag 配对堆，这个是最推荐使用的
• thin_heap_tag 斐波那契堆，这个其实复杂度最优秀，但是实际由于常数等因素的影响实际配对堆更优
• binomial_heap_tag：二项堆，没啥用吧只能说
• binary_heap_tag：二叉堆，呵呵

值得吐槽的是，配对堆也是唯一一个复杂度没能完全证明的

函数

你得知道 stl 里面那个萎了的堆有的函数他都是有的

唯一需要注意的是一个有趣的地方，这里的 push 是有返回值的，会返回一个迭代器

modify修改

依赖于迭代器才能实现的修改

注意的是 pbds 的迭代器叫做 point_iterator

我们可以用一个迭代器数组存下每个元素对应的位置，这样就可以快速修改元素了~

迭代器的声明方式：

__gnu_pbds::priority_queue::point_iterator it

修改的方式是：

q.modify(it,val)

含义是把迭代器 it 位置的元素改为 $val$

迭代器数组的初始化是 NULL，我们也可以借助一个元素对应的迭代器是不是 NULL 来判断一个元素在不在队列里

来，我们利用这个玩意来写一个dijskra

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define int long long
using namespace __gnu_cxx;
using namespace __gnu_pbds;
using namespace std;
const int N=2e5+5;
const int inf=1e12;
typedef pair<int,int> pii;
vector<pii> e[N];
__gnu_pbds::priority_queue<pii,greater<pii>,pairing_heap_tag> q;
__gnu_pbds::priority_queue<pii,greater<pii>,pairing_heap_tag>::point_iterator its[N];
int dis[N];
int n,m,s;
void dijskra(int s){
    q.clear();
    for(int i=1;i<=n;i++) dis[i]=inf;
    its[s]=q.push({0,s});
    dis[s]=0;
#define v g.first
#define w g.second
    while(!q.empty()){
        int u=q.top().second;
        q.pop();
        for(auto g:e[u]){
            if(dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                if(its[v]==NULL){
                    its[v]=q.push({dis[v],v});
                }else{
                    q.modify(its[v],{dis[v],v});
                }
            }
        }
    }
#undef v
#undef w
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++){
        int u,v,w;
        cin>>u>>v>>w;
        e[u].push_back(make_pair(v,w));
    }
    dijskra(s);
    for(int i=1;i<=n;i++) cout<<dis[i]<<" ";
}

这样的理论复杂度是比正常的其实要好的，但是由于常数原因咳咳

但是确实很好玩

join合并

是的~这是可并堆哦

使用方法：

a.join(b);

会把 $b$ 中元素全部扔到 $a$ 中并自动清空 $b$

我们借助这个玩意可以写左偏树的板子：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
using namespace __gnu_pbds;
const int N=1e5+5;
typedef pair<int,int> pii;
__gnu_pbds::priority_queue<pii,greater<pii>,pairing_heap_tag> q[N];
int n,m;
int fa[N];
bool del[N];
int find(int x){
    return (x==fa[x]?x:(fa[x]=find(fa[x])));
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        q[i].push(make_pair(x,i));
        fa[i]=i;
    }
    while(m--){
        int opt,x,y;
        cin>>opt>>x;
        if(opt==1){
            cin>>y;
            int fx=find(x),fy=find(y);
            if(fx==fy or del[x] or del[y]) continue;
            q[fx].join(q[fy]);
            fa[fy]=fx;
        }
        else{
            if(del[x]) {cout<<"-1\n";continue;}
            int fx=find(x);
            cout<<q[fx].top().first<<"\n";
            del[q[fx].top().second]=1;
            q[fx].pop();
        }
    }
}

慢是慢你就说是不是不需要脑子吧

hash_table

pbds 提供了一个非常好用的哈希表，简单来说就反正比 unordered_map 好的多，没那么容易被卡，速度也快很多

一定要注意的是，hash_table 对标的是 unordered_map 不是 map，他的复杂度是线性的，而且不支持排序，不要拿他和 map 比较了，没有意义功能都不一样

概述

两种哈希表：
- cc_hash_table<T,T>这是拉链法
- gp_hash_table<T,T> 这个是探测法

经测试，cc 的读入输出会比 gp 略微快一些，但是 gp 仅仅是牺牲了大约百分之十的读写速度就换来了快 $3$ 到 $6$ 倍的插入删除和清除速度，是更为划算的，大多数情况都建议选用 gp，但是必须注意的是不是任意时候

一个例子是OIFC20241023，本题中我的代码在 unordered_map 是有概率能过（看评测机状态，众所周知xyd的评测机波动巨大），使用 gp 只有 $65$，然后 cc 稳定可以过

原因是此时的 hash 的主要作用在于映射，也就是读写部分，此时 gp 在读写的劣势会被放大，也就是说当不怎么需要多次插入删除而主要需要读取数值的时候， cc 会比 gp 更为优秀

在给出的例子中的原因主要是插入次数顶多是 $n$ 级别的，但是查询是 $26n$ 级别的，当然这还是不能解释为什么比 unordered_map 还要慢

rope

一个奇怪的东西

值得注意的是rope的复杂度有点鬼，有人认为底层是块状链表，那复杂度就是根号，有人说是可持久化平衡树，那复杂度就是对数，本文暂时写作根号，假如有一天确定了是对数那就自动把本文所有根号看成对数吧

rope 的声明

rope<T> s

跟什么栈啊队列啊是一样的，支持结构体，空间动态

强制转化类型与赋值

int f[114514],n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++) cin>>f[i];
    rope<int> fa(f);
    for(int v:fa) cout<<v<<endl;
}

但是注意被用于转化的普通数组的下标 $0$ 处必须非 $0$，比较逆天

字符串rope（crope）

crope c;
rope<char >c;

这两种写法是等价的

函数如下：

crope c;
c.push_back(x);//在c末尾添加x
c.insert(p,x);//在c下标为p的位置插入一个x
c.insert(p,s,n);//将字符串 s 的前n位插在p处
c.erase(p,x);//从下标p处开始删除x个元素
c.replace(p,s);//从下标p开始把字符串s覆盖上去
c.copy(p,n,s);//从下标p开始的n个字符换成字符串s
c.substr(p,x);//从p开始截取x个元素
c[x]/c.at(x);//访问元素
c.append(s,p,n);
//把字符串 s 中从下标 p 开始的 n 个字符连接到 a 的结尾
//如没有参数 n 则把字符串 s 中下标 p 后的所有字符连接到 a 的结尾
//如参数 p 也没有则把整个字符串 s 连接到 a的结尾

除了 push_back这种单个元素操作以外复杂度都是根号

数组rope

其实同理

数组rope 额外可以用 append(x) 来尾端插入一个数字 $x$

当然常见的size什么的函数当然是都有的

运用——可持久化操作

例题

怎么实现

是的没错暴力存每个版本就可以了

你说空间？这题能过，考场上骗分多好用啊

值得注意的是rope互相直接赋值的复杂度也是神奇的根号

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef double db;
typedef pair<int,int> pii;
#define mpi make_pair
const int N=2e5+5;
const int mod=998244353;
crope now,pst[N];
int cnt,n;
int main(){
    cin>>n;
    while(n--){
        char opt;
        cin>>opt;
        if(opt=='T'){
            char x;
            cin>>x;
            now.push_back(x);
            pst[++cnt]=now;
        }else if(opt=='U'){
            int q;
            cin>>q;
            now=pst[cnt-q];
            pst[++cnt]=now;
        }else{
            int q;
            cin>>q;
            cout<<now[q-1]<<"\n";
        }
    }
}

tree平衡树

pbds 的平衡树必须注意的是速度问题，常数较为巨大，相比手写根据网上数据大概会比相同的手写慢个六分之一，这是封装必然的代价

附录

个人常用头文件与 define 等：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
typedef double db;
typedef pair<int,int> pii;
#define mp make_pair