这篇blog 介绍，GNU对STL的一个扩展库 Policy-Based Data Structures,PBDS，的一些应用，会持续更新

introduction

pbds 是GNU对STL的一个扩展，封装了很多常见的数据结构，并且提供了操作数据结构内部metadata的策略，也就是说user(我们)可以直接对内部节点更新了，这称之为 policy。这里并不打算详细介绍 pbds的使用和设计，instead，这里仅仅提供一些案例，它的使用可见官方手册

pbds 封装这样一些数据结构:

tree
hash_table
priority_queue
trie

并且提供比STL更加通用的操作方式

tree

template<
typename Key,// key 类型
typename Mapped,// value 类型，可为null_type, 表示set
typename Cmp_Fn = std::less<Key>,
typename Tag = rb_tree_tag,// other rb_tree_tag, splay_tree_tag, or ov_tree_tag
template<
typename Const_Node_Iterator,
typename Node_Iterator,
typename Cmp_Fn_,
typename Allocator_>
class Node_Update = null_node_update,// update policy，大部分情况下不用自己写
typename Allocator = std::allocator<char> >
class tree;

tree 与STL中的map和set非常类似，不过由于提供了对node的metadata的操作使得我们能够解决一些set和map无法解决的东西。

order 查询

最典型的一种情形就是 set 无法告诉你某个 key的前面有多少元素，然而我们知道通过维护一些节点上的metadata(算法导论)，可以实现这个操作，斌且不需要任何额外的时间开销

typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

以上将node update policy 设置为 statistic，能够实现 order_of_key,find_by_order的操作

    ordered_set X;
    X.insert(1);
    X.insert(2);
    X.insert(4);
    X.insert(8);
    X.insert(16);

    cout<<*X.find_by_order(1)<<endl; // 2
    cout<<*X.find_by_order(2)<<endl; // 4
    cout<<*X.find_by_order(4)<<endl; // 16
    cout<<(end(X)==X.find_by_order(6))<<endl; // true

    cout<<X.order_of_key(-5)<<endl;  // 0
    cout<<X.order_of_key(1)<<endl;   // 0
    cout<<X.order_of_key(3)<<endl;   // 2
    cout<<X.order_of_key(4)<<endl;   // 2
    cout<<X.order_of_key(400)<<endl; // 5

静态范围查询的一个例子

KickStart 2019 G C

这题在实际中我用暴力+剪枝的方式解决了，其实可以有更简单的做法 $O(3^{N/2}\log 3^{N/2})$,或者 $2^N$

这里说一下前者，后者可见 lzy

其实就是折半查找，我们先枚举出所有的前 $N/2$ 与后 $N/2$ 的所有状态vector<pair<LL,LL> > pre,last，

每个状态表示为 <v1,v2>,分别代表此状态下 $a,b$ 得到的分数,这样我们就可以把问题规约到:

对于前半段的每个状态，<v1,v2> 我们在后面一个状态集合 last 中查找 $\#\{S|S.first >= H-v_1,S.second >=H-v2\}$ 的数目就行了

这个问题等价于在二位平面上做范围查询，可以用range tree处理，不过我是不会敲的，所以可以采用 pbds 给我们提供的利器，做静态查找

把这个问题抽象一下:

给一个集合 $S=\{<a_i,b_i>\}$,Q个查询，每个查询为 $c,d$ 询问 $a_i\ge c,b_i \ge d$ 点有多少个

解决方案

将 $Q$ 个查询保存下来按照第一维由大到小排序，同时将 S 按照第一维由大到小排序，有一个指针扫描 S，维护指针经过位置的所有 $b_i$ 的值的集合，统计其中大于等于询问 $d_j$ 的元素个数

伪代码:

multiset v2
idx = 0
ans = 0
for e in Q:
    while idx< S.size() and S[idx].first>=v2:
        v2.insert(S[idx].second)
    ans += # {Se|Se in v2,Se >= e.second}

最后一行就可以用 pbds中的tree实现了，

细节处理同元素的问题，一个方法是通过 pair，第二位表示同元素的id，这样就能很简单的处理了

完整代码

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define ms(x,v) memset((x),v,sizeof(x))
#define INF 0x3f3f3f3f
using namespace std;
using namespace __gnu_pbds;

const int MAXN = 100+10;
typedef long long LL;

typedef tree<pair<LL,int>,
null_type,
less<pair<LL,int>>,
rb_tree_tag,
tree_order_statistics_node_update> ordered_tree;


LL N,H;

pair<LL,LL> val[MAXN];
LL sa[MAXN],sb[MAXN];

LL pow3[MAXN];

void dfs(vector<pair<LL,LL> >&ans,LL v1,LL order_v2,int idx,int bound=N){//0,...,N-1
    
    if(idx == bound){
        ans.push_back(make_pair(v1,order_v2));
        return;
    }
    dfs(ans,v1 + val[idx].first,order_v2,idx+1,bound);
    dfs(ans,v1,order_v2+val[idx].second,idx+1,bound);
    dfs(ans,v1+val[idx].first,order_v2 + val[idx].second,idx+1,bound);
}


void solve(){
    cin >> N >> H;
    for(int i=0 ; i<N ; ++i)cin >> val[i].first;
    for(int i=0 ; i<N ; ++i)cin >> val[i].second;
    if(N==1){
        int ans = H>0 ?(val[0].first >= H && val[0].second >=H ) : 3;
        cout << ans << "\n";
        return;
    }
    vector<pair<LL,LL> >pre;
    vector<pair<LL,LL> >last;
    dfs(pre,0,0,0,N/2);
    dfs(last,0,0,N/2,N);
    sort(pre.begin(),pre.end());
    sort(last.rbegin(),last.rend());
    
    ordered_tree order_v2;

    unordered_map<LL,int> cnt;

    LL ans =0;
    int idx = 0;
    for(const auto & e : pre){
        LL bd = H - e.first;
        while(idx < last.size() && last[idx].first >=bd){
            int id = cnt[last[idx].second]++;
            order_v2.insert(make_pair(last[idx].second,id));
            idx ++;
        }
        LL x = H - e.second;
        ans += order_v2.size() -  order_v2.order_of_key(make_pair(x,-1));

    }
    cout << ans << "\n";
}





int main(){
    ios :: sync_with_stdio(0);
    cin.tie(0);
    // cout.tie(0);
    std::cout.precision(10);
    std::cout.setf( std::ios::fixed, std:: ios::floatfield );
    pow3[0] =1;
    for(int i=1 ; i<=20;++i)pow3[i] = pow3[i-1] * 3;
    int T;
    cin >> T;
    for(int tt =1 ; tt <=T ; ++tt)
    {
        cout << "Case #" << tt << ": ";
        solve();
    }
    
 
    return 0;
}

priority_queue

pbds 里面的 priority_queue 实在是太强了，居然支持对元素的访问和修改。简直是解决了STL里面的PQ的痛点。想想当初写对优化的dijkstra的痛点，由于STL不支持节点修改，只好每次都把val从新仍到堆了，导致了很多额外的开销，甚至还有高中生在算法竞赛中专门研究hack这个东西的算法…

template<
    typename Value_Type,
    typename Cmp_Fn = std::less<Value_Type>,
    typename Tag = pairing_heap_tag,
    typename Allocator = std::allocator<char> >
class priority_queue;

除了STL里面优先队列的 push 与 pop 之外，pbds还支持了 modify(iterator,val),与erase

同时它的底层实现了几种堆tag,

 pairing_heap_tag, 
 binary_heap_tag, 
 binomial_heap_tag, 
 rc_binomial_heap_tag, 
 thin_heap_tag,

thin_heap 是一种const 比斐波那契堆还小堆，pairing_heap,几乎是最常用的，复杂度和常数都足够小

具体复杂度见官网ref

基于对优化的dijkstra 单源最短路算法测试

题目链接 luogu P4779

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define ms(x,v) memset((x),v,sizeof(x))
#define INF 0x3f3f3f3f
#define pbds __gnu_pbds
using namespace std;
 
const int MAXN = 1000+10;
typedef long long LL;
const LL MOD = 1e9+7;

typedef __gnu_pbds::priority_queue<
pair<int,int>,
greater<pair<int,int>>,
__gnu_pbds::pairing_heap_tag
> PQ_pair;


void dijstra(vector<int>&dist,const vector<vector<pair<int,int> > > &G,int S =0){
    // node idx base 0,...,G.size() -1
    dist.resize(G.size());
    fill(dist.begin(),dist.end(),INF);

    PQ_pair Q;
    vector<PQ_pair::point_iterator> it(G.size(),NULL);
    dist[S] =0;
    Q.push(make_pair(0,S));

    while (!Q.empty())
    {
        const auto & top = Q.top();
        int u = top.second;
        int dis = top.first;
        Q.pop();
        for(const auto & edge : G[u]){
            int v = edge.first;
            int dv= dis + edge.second;
            if(dv < dist[v]){
                dist[v] = dv;
                if(it[v] == NULL)it[v] = Q.push(make_pair(dv,v));
                else Q.modify(it[v],make_pair(dv,v));// assert it[v] in Q
            }
        }
    }
}

void solve(){
    int N,M,S;
    cin >> N >> M >> S;S--;
    vector<vector<pair<int,int> > > G(N);
    for(int i=0 ; i<M ; ++i){
        int u,v,w;
        cin >> u >> v >> w;
        u --;
        v --;
        G[u].push_back({v,w});
    }
    vector<int> dist;
    dijstra(dist,G,S);
    cout << dist[0];
    for(int i=1 ; i<N ; ++i)
        cout << " " << dist[i];
}

int main(){
    ios :: sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    std::cout.precision(10);
    std::cout.setf( std::ios::fixed, std:: ios::floatfield );
    
    solve();
    return 0;
}

我测了各种不同的堆tag，除了 binary_heap 外其他堆均可以通过这个题目，其中pairing_heap 最快，总共用时 450ms, thin_heap 次之，可见分摊复杂度的常数可能还是pairing_heap 小一些。thin_heap 暂时还没研究过，虽然提供了 modify的嘴啊坏复杂度保证，但是分摊复杂度的常数还是比 pairing_heap 小了一些。

reference

Chapter 21. Policy-Based Data Structures
Chanis 的博客.比STL还STL？——平板电视
codeforces.C++ STL: Policy based data structures
GNU priority_queue

版权声明

本作品为作者原创文章，采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

作者: taotao

仅允许非商业转载，转载请保留此版权声明，并注明出处

pbds: STL 的扩展数据结构