簡介Policy-Based Data Structures ( __gnu_pbds )


前言：

__gnu_pbds全名為GNU Policy-Based Data Structures，競賽中俗稱黑魔法，因為其內建了許多強大的工具，例如：可合併堆、伸展樹、紅黑樹、字典樹、hash table...，不過因為他放在一個很奇怪的標頭檔底下，且不是所有編譯器都支援(從名稱就知道那是GNU的東西)，所以也沒那麼多人會使用他。

1. 使用方法

要使用其的資料結構時，請先引入ext/pb_ds/assoc_container.hpp，若要使用priority_queue時則還要多引入ext/pb_ds/priority_queue.hpp，而那些東東都包在__gnu_pbds這個namespace底下，所以如果懶的話，可以全部把他倒出來。
p.s不過如果std的也倒出來priority_queue會衝突到，此時建議還是要加個__gnu_pbds::在前面
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

2. priority_queue

可合併堆是我第一個知道的功能，那我們先看看他的type模板到底寫了甚麼吧
template<
    typename Value_Type,
    typename Cmp_Fn = std::less<Value_Type>,
    typename Tag = pairing_heap_tag,
    typename Allocator = std::allocator<char> >
class priority_queue;

這裡最常會動到的大概就是Value_Type跟Cmp_Fn了吧

  • Value_type 顯然是你的資料型別
  • Cmp_Fn 則是一個物件，其必須包含一個bool operator()，他會用來比較你的兩個資料，以知道誰該在你呼叫top時出現
  • 比較神奇的一個東東是Tag，預設為paring_heap_tag，也就是說他預設配對堆，不過他也支援其他種類的堆，以下列出其所有支援的堆的tag及其複雜度
    pushpopmodifyerasejoin
    pairing_heap_tagO(1)worst:Θ(n)
    amortized:Θ(log n)    		worst:Θ(n)
    amortized:Θ(log n)    		worst:Θ(n)
    amortized:Θ(log n)    		O(1)
    binary_heap_tagworst:Θ(n)
    amortized:O(log n)    		worst:Θ(n)
    amortized:Θ(log n)    		Θ(n)Θ(n)Θ(n)
    binomial_heap_tagΘ(log n)Θ(log n)Θ(log n)Θ(log n)Θ(log n)
    rc_binomial_heap_tagO(1)Θ(log n)Θ(log n)Θ(log n)Θ(log n)
    thin_heap_tagO(1)worst:Θ(n)
    amortized:Θ(log n)    		worst:Θ(log n)
    amortized:O(1)    		worst:Θ(n)
    amortized:Θ(log n)    		Θ(n)
  • Allocator則通常不會動到

基本上就看自己需求調參數囉，不過大多時間配對堆還是有在支援所有操作下最少的時間耗用，所以若沒有要特化某個功能，還是建議用預設的就好了。

而其可支援的操作包含了
  • pq.begin() 回傳他最前面的iterator (值得注意的是他的iterator是單向的那種)
  • pq.end() 回傳一個iterator指向一個空的節點
  • pq.empty() 回傳當前的pq是否為空
  • pq.clear() 把整個pq清乾淨
  • pq.size() 回傳當前pq的大小
  • pq.top() 回傳位於pq中的極值
  • pq.push(x) 把x放入priority_queue中，並回傳一個iterator指向那個元素
  • pq.pop() 把當前極值從pq中刪除
  • pq.modify(it,x) 把it指到的元素改成x
  • pq.join(qp) 把qp中的元素都搬到當前這個pq，並清空qp
  • pq.erase(it) 把it指到的元素從pq中移除
剩下詳細的功能可以參見其官方文件

3. tree

同樣，先來看看模板吧XD
template<
    typename Key,
    typename Mapped,
    typename Cmp_Fn = std::less<Key>,
    typename Tag = rb_tree_tag,
    template<
        typename Const_Node_Iterator,
        typename Node_Iterator,
        typename Cmp_Fn_,
        typename Allocator_>
    class Node_Update = null_tree_node_update,
    typename Allocator = std::allocator<char> >
class tree;

他的基本用法跟Map一樣(Map底層也是紅黑樹)

  • Key 就是你鍵值的type，如果less不知原你的type的話，你還要自己寫個Cmp_Fn (跟map一樣)
  • Mapped 就是你要存的資料的型別，如果設為null_type的話你的樹會變成跟set一樣，iterator也會從pair退化回Key，不過速度會有小幅的成長
  • Cmp_Fn 他吃一個class，跟stl::map吃的cmp_fn一樣
  • Tag 也是算有點神奇，只接受rb_tree_tag, ov_tree_tag, splay_tree_tag，不過大多時間用起來還是預設的紅黑樹最快
  • Node_Update是這裡面比較重要的一個，預設是null_tree_update。不過在引入tree_policy.hpp的前提下，當你改成tree_order_statistics_node_update後他會突然出現兩個可以使用的函數: find_by_order跟order_of_key前者可以讓你找到第k小(大)的資料是誰，後者可以讓你知道有多少資料的鍵值小(大)於k，不過更神奇的是他其實是可以自訂的!!
這邊稍微介紹一下該怎麼自訂Node_Update，底下再貼一下tree支援的操作
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;
};
上面那串根據《C++的pb_ds库在OI中的应用》來看似乎是一定要的(當然struct名可以自訂)，不過我自己是覺得metadata_type應該是可以自己任意設的(當然int可以改long long是沒差的)

...未完待續

參考資料

留言

張貼留言

這個網誌中的熱門文章

[TIOJ] 1094. C.幼稚國王的獎賞

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); int ret = 0; if(nodes[cur].rc) ret = query(x, nodes[cur].rc, d-1) + two(d); else ret = query(x, nodes[cur].lc, d-1); if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); return ret; } public: void init(){
閱讀完整內容

[Codeforces] 731F. Video Cards

題目連結: http://codeforces.com/problemset/problem/731/F 惹...原來可以暴力做。直接枚舉每個人$i$當作leader時的情況，而計算時就是要算$[ik, i(k+1))$的數字數有幾個，因為在這區間的數字$a$再扣完之後一定都變成$ik$。此外枚舉倍數是$nlogn$的(某種調和級數的想法)，所以就照著做囉(? #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 200000 + 5; lld sum[N]; bool isok[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ int x; cin>>x; sum[x]++; isok[x]=1; } for(int i=1;i<N;i++) sum[i]+=sum[i-1]; lld ans = 0; for(int i=1;i<N;i++){ if(!isok[i]) continue; lld cur = 0; for(int j=i;j<N;j+=i) cur += j*(sum[min(j+i,N)-1]-sum[j-1]); ans = max(ans, cur); } cout<<ans<<'\n'; return 0; }
閱讀完整內容

[IOJ] 19. 啦啦啦

題目連結: http://ioj.infor.org/problems/19 因為$xor$有神奇(?的性質$a \oplus b = c \Longrightarrow a \oplus c = b$，所以就$O(n)$掃過去建好表，再$O(n)$掃一遍加起來，值得注意的是因為$a \oplus 0 = a$，所以若$x=0$，那要再減掉所有數的個數(自己不能算) #include <stdio.h> void gn(int &_){ _=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar(); } int MiccWan[100000 + 10]; int wayneTu[1000000 + 10] = {0}; int main(){ int t,x; long long edisonhello=0; gn(t);gn(x); for(int i=0;i<t;i++){ gn(MiccWan[i]); wayneTu[MiccWan[i]^x]++; } for(int i=0;i<t;i++){ edisonhello+=wayneTu[MiccWan[i]]; } if(x==0) edisonhello-=t; printf("%lld",edisonhello>>1); return 0; }
閱讀完整內容