NOI系列竞赛可用的非主流技巧

LiuTianyou · 2022-07-22 10:45:41 · 个人记录

• 摘要
• pb_ds库
  • 简介
  • 使用
  • 哈希表
    • cc_hash_table - 拉链法
    • gp_hash_table - 探测法
    • 哈希表效率测试
  • 平衡树
    • 平衡树效率测试
      • 1号环境测试
      • 2号环境测试
      • 3号环境测试
  • Trie树
  • 堆
  • 进阶教程
    • __gnu_pbds::tree 的遍历
    • __gnu_pbds::trie的遍历
    • 堆
  • 手写节点更新器
    • 手写__gnu_pbds::tree的节点更新器
• rope库
  • 简介
  • 定义
  • 使用
• STL库
  • 最大值/最小值函数
  • min()与max()的列表版本
  • minmax_element(begin, end)
  • 数列类函数
  • shuffle(begin, end, gen) \& is_sorted(begin, end)
  • iota(begin, end, value)
  • prev_permutation(begin, end) \& next_permutation(begin, end)
  • count(begin, end, value) \& count_if(begin, end, func) \& replace(begin, end, value1, value2) \& fill(begin, end, value) \& copy(begin, end, begin2) \& find(begin, end, value)
  • accumulate(begin, end, value)
  • partial_sum(begin, end, begin2) \& adjacent_difference(bg1,ed1,bg2)
  • inplace_merge(begin, mid, end)
  • 其它
  • function<>
• Q&A
  • pbds带的平衡树不能支持重复元素吗
• 参考文献

0xFF 摘要

本篇文章介绍了NOI系列竞赛被允许使用的一些非常规做法，其包括pb_ds库的使用、rope库的使用、部分不太常见的STL库用法.

主要介绍了pb_ds库的使用，并使用大量数据分析了手写、STL库、pb_ds库的效率，从数据上证明了在赛时开O2优化的情况下，pb_ds库更快，而且简单.

作者希望在NOI竞赛可用的前提下通过这篇文章普及这些不太常见但好用的方法.

0x00 pb_ds库

0x01 简介

pb_ds库全称为Policy-Based Data Structures，即基于策略的数据结构库.其中包含很多常见且有用的数据结构，可以供大家使用.^{[10]}

由于 pb_ds 库的主要内容在以下划线开头的 __gnu_pbds 命名空间中，在 NOI 系列活动中的合规性一直没有确定.2021 年 9 月 1 日，NOI允许使用以下划线开头的库函数或宏（但具有明确禁止操作的库函数和宏除外），在 NOI 系列活动中使用 pb_ds 库的合规性有了文件上的依据^{[1]}.

同时目前NOI系列竞赛的编译指令增加了-O2选项，这为pb_ds库的使用提供了更多可能.^{[2]}

0x02 使用

pb_ds是GNU的扩展库，所以和标准库要包含的头文件不同.

#include <ext/pb_ds/assoc_container.hpp> //只要使用pb_ds库，就要包含
#include <ext/pb_ds/hash_policy.hpp> //哈希表使用
#include <ext/pb_ds/priority_queue.hpp> //堆使用
#include <ext/pb_ds/tree_policy.hpp> //平衡树使用
#include <ext/pb_ds/trie_policy.hpp> //字典树使用

扩展pb_ds都在命名空间__gnu_pbds中，所以需要加上前缀__gnu_pbds::才能使用.^{[11]}

0x03 哈希表

哈希表又称散列表，是算法竞赛的一大杀器.熟练使用哈希表可以为你的离散化增添光彩. 在这里相当于std::unordered_map.

__gnu_pbds::cc_hash_table<T1, T2> h;
__gnu_pbds::gp_hash_table<T1, T2> h;

0x04 cc_hash_table - 拉链法

如果遇到哈希冲突，拉链法哈希会尝试在同一个位置拉一条链表，每次访问的时候会遍历下链表，确认你需要的值.

这种哈希表速度可能会慢一些，但是推荐使用.

0x05 gp_hash_table - 探测法

如果遇到哈希冲突，就会检查下一个位置是否有值.如果没有，就放进去，最后实现避免冲突

拉链法不会被出题人卡掉，但是探测法可以.^{[4]}

对于使用，支持operator[]()和find()，同std::unordered_map使用.

P3370 【模板】字符串哈希

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace std;
__gnu_pbds::cc_hash_table<string, bool> bucket;
signed main(){
    int n, ans = 0;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        char buffer[10000];
        scanf("%s", buffer);
        if(bucket[buffer] == false) ans++;
        bucket[buffer] = true;
    }
    printf("%d\n", ans);
    return 0;
}

时间测试^{[16]}：

0x30 哈希表效率测试

测试环境：Windows 11 + Lemon

CPU型号：Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz （12线程）

编译器：TDM-GCC 10.3.0

数据为P1097 [NOIP2007 提高组] 统计数字的加强版，n = 10^7，有10^5个不同的数字，测试点100个.

（注：答案错误是因为除了map以外的所有实现不带排序，为了方便不写spj而做的）

不开O2优化的情况下得到结果：

开启O2优化的情况下得到结果：

可以看出gp_hash_table在随机情况下比cc_hash_table快，二者碾压unordered_map

而三者以\Theta(1)的复杂度碾压map\Theta(\log n)的复杂度.

0x06 平衡树

要了解平衡树，首先需要了解二叉查找树（Binary Search Tree, BST）.

在一个BST中，对于每一个节点，满足： ^{[5]}

• 其左子树任意一点的权值都小于该节点的权值.

• 其右子树任意一点的权值都大于该节点的权值.

BST的中序遍历得到的数列单调递增.

为了保证BST的平衡（即对于任意一点，不会出现左子树大小严重大于右子树的情况），我们设计了平衡树.

我们可以采用旋转、分裂等奇怪的动作，维护一个等效的BST，且平衡.

平衡树可以实现在\Theta(\log(n))时间内维护一个序列有序并双向查找其排名.

定义一个平衡树^{[6]}：

__gnu_pbds::tree<Key, Mapped, Cmp_Fn = std::less<Key>, 
    Tag = __gnu_pbds::rb_tree_tag,
    Node_Update =  __gnu_pbds::null_tree_node_update,
    Allocator = std::allocator<char> >

key表示存储的元素类型.

Mapped表示映射规则（Mapped-Policy），可以为__gnu_pbds::null_type，表示你希望这是一个类似于std::set的集合. 也可以是另外一个类型，表示你希望这个数据结构像std::map.

Cmp_Fn表示关键字比较类型，可以为std::less<Key>或std::greater<Key>等.

Tag表示选择的平衡树类型，有下列三种：

• __gnu_pbds::rb_tree_tag：红黑树，常用这个

• __gnu_pbds::splay_tree_tag：Splay树

• __gnu_pbds::ov_tree_tag：一个排序的vector而已

Node_Update：更新节点策略，使用__gnu_pbds::tree_order_statistics_node_update之后才能开启order_of_key与find_by_order方法.

Allocator：空间分配器（一般不用）

给出几个有意思的例子：

__gnu_pbds::tree<int, bool> //相当于map<int, bool>
__gnu_pbds::tree<int, bool, std::greater<int> > //相当于递减的map<int, bool>
__gnu_pbds::tree<int,  __gnu_pbds::null_type> //相当于set<int>
__gnu_pbds::tree<int,  __gnu_pbds::null_type, std::greater<int> > //相当于递减的set<int>

操作同map，为以下几种：

• insert(x) 插入一个数x，返回std::pair<point_iterator, bool>，bool表示操作是否成功.

• erase(x) 删除元素/迭代器x，返回bool表示操作是否成功.

• order_of_key(x) 返回x的排名（排名从0开始）

• find_by_order(x) 寻找第x名（排名从0开始）的迭代器

• lower_bound(x)/upper_bound(x) 二分查找x，返回迭代器

• join(x) 将树x并入当前树，树x被删除（树x与当前树类型一致）

• split(x, b) 将当前树分为两个树，一个树小于等于x，一个树大于x

• empty()/size() 返回是否为空/大小

如果有重复的数据，那么情况就不一样了.你需要使用pair<int, int>将数据强行转为不重复的，所以我们有了以下代码.

P6136 【模板】普通平衡树（数据加强版）

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define I64 "%d"
__gnu_pbds::tree<std::pair<int, int>, __gnu_pbds::null_type, std::less<std::pair<int, int> >, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> data;
signed main(){
    int n, m, cnt = 0, last = 0, ans = 0;
    scanf(I64 I64, &n, &m);
    for(int i = 1, t; i <= n; i++){
        scanf(I64, &t);
        data.insert(std::make_pair(t, cnt++));
    }
    for(int i = 1; i <= m; i++){
        int op, x;
        scanf(I64 I64, &op, &x);
        x ^= last;
        if(op == 1){
            data.insert(std::make_pair(x, cnt++));
        }else if(op == 2){
            auto it = data.lower_bound(std::make_pair(x, 0));
            data.erase(it);
        }else if(op == 3){
            last = data.order_of_key(std::make_pair(x, 0)) + 1;
        }else if(op == 4){
            last = data.find_by_order(x  - 1)->first;
        }else if(op == 5){
            last = data.find_by_order(data.order_of_key(std::make_pair(x, 0)) - 1)->first;
        }else{
            last = data.find_by_order(data.order_of_key(std::make_pair(x, 2147483647)))->first;
        }
        if(op > 2) ans ^= last;
    }
    printf(I64 "\n", ans);
    return 0;
}

P3380 【模板】二逼平衡树（树套树）

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> RbTree;
struct SegmentTree {
    int left, right;
    RbTree* Tree;
} STree[1000010];
int arr[1000010], cnt = 0;
void build(int p, int l, int r) {
    STree[p].left = l, STree[p].right = r;
    STree[p].Tree = new RbTree;
    for(int i = l; i <= r; i++) {
        STree[p].Tree->insert(make_pair(arr[i], cnt++));
    }
    if(l != r) {
        int mid = (STree[p].left + STree[p].right) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
    }
    return;
}
void modify(int p, int place, int value) {
    auto it = STree[p].Tree->lower_bound(make_pair(arr[place], 0));
    STree[p].Tree->erase(it);
    STree[p].Tree->insert(make_pair(value, cnt++));
    if(STree[p].left == STree[p].right) {
        return;
    }
    int mid = (STree[p].left + STree[p].right) / 2;
    if(place <= mid)
        modify(p * 2, place, value);
    else
        modify(p * 2 + 1, place, value);
    return;
}
int askRank(int p, int l, int r, int k) {
    if(STree[p].left > r || STree[p].right < l)
        return 0;
    if(STree[p].left >= l && STree[p].right <= r)
        return STree[p].Tree->order_of_key(make_pair(k, 0));
    return askRank(p * 2, l, r, k) + askRank(p * 2 + 1, l, r, k);
}
int askNum(int u, int v, int k){
    int l = 0, r = 1e8;
    while(l < r) {
        int mid = (l + r + 1) / 2;
        if(askRank(1, u, v, mid) < k)
            l = mid;
        else
            r = mid - 1;
    }
    return r;
}
int askPre(int p, int l, int r, int k) {
    if(STree[p].left > r || STree[p].right < l)
        return -2147483647;
    if(STree[p].left >= l && STree[p].right <= r){
        int i = STree[p].Tree->order_of_key(make_pair(k, 0));
        if(i == 0) return -2147483647;        
        int ret =  STree[p].Tree->find_by_order(i - 1)->first;
        return ret;
    }
    return max(askPre(p * 2, l, r, k), askPre(p * 2 + 1, l, r, k));
}
int askSuf(int p, int l, int r, int k) {
    if(STree[p].left > r || STree[p].right < l)
        return 2147483647;
    if(STree[p].left >= l && STree[p].right <= r){
        int i = STree[p].Tree->order_of_key(make_pair(k, 2147483647));
        if(i >= STree[p].Tree->size()) return 2147483647;        
        int ret = STree[p].Tree->find_by_order(i)->first;
        return ret;
    }
    return min(askSuf(p * 2, l, r, k), askSuf(p * 2 + 1, l, r, k));
}
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        scanf("%d", &arr[i]);
    }
    build(1, 1, n);
    while(m--){
        int opt, a, b, c;
        scanf("%d %d %d", &opt, &a, &b);
        switch(opt){
            case 1:
                scanf("%d", &c);
                printf("%d\n", askRank(1, a, b, c) + 1);
                break;
            case 2:
                scanf("%d", &c);
                printf("%d\n", askNum(a, b, c));
                break;
            case 3:
                modify(1, a, b);
                arr[a] = b;
                break;
            case 4:
                scanf("%d", &c);
                printf("%d\n", askPre(1, a, b, c));
                break;
            case 5:
                scanf("%d", &c);
                printf("%d\n", askSuf(1, a, b, c));
                break;
        }
    }
    return 0;
}

上述程序开O2后可以通过，时间为8.05s，优于部分手写的程序.

P1975 [国家集训队]排队

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> RbTree;
RbTree* STree[1000010];
int arr[1000010], b[1000010], w[1000010], cnt = 0, n, m, ans = 0;
void Merge_Sort(int l, int r) {
    if(l == r) return;
    int mid = (l + r) >> 1;
    Merge_Sort(l, mid);
    Merge_Sort(mid + 1, r);
    int i = l, j = mid + 1, k = l;
    while(i <= mid && j <= r) {
        if(arr[i] > arr[j])
            ans += mid - i + 1, w[k++] = arr[j++];
        else
            w[k++] = arr[i++];
    }
    while(i <= mid) w[k++] = arr[i++];
    while(j <= r) w[k++] = arr[j++];
    for(int i = l; i <= r; i++) arr[i] = w[i];
}
void Insert(int p, int l, int r, int place, int value) {
    if(STree[p] == nullptr) STree[p] = new RbTree;
    STree[p]->insert(make_pair(value, cnt++));
    if(l == r) return;
    int mid = (l + r) / 2;
    if(place <= mid)
        Insert(p * 2, l, mid, place, value);
    else
        Insert(p * 2 + 1, mid + 1, r, place, value);
    return;
}
void Delete(int p, int l, int r, int place, int value) {
    STree[p]->erase(STree[p]->lower_bound(make_pair(value, 0)));
    if(l == r) return;
    int mid = (l + r) / 2;
    if(place <= mid)
        Delete(p * 2, l, mid, place, value);
    else
        Delete(p * 2 + 1, mid + 1, r, place, value);
    return;
}
int askMin(int p, int l, int r, int ql, int qr, int v) {
    if(ql <= l && r <= qr) {
        int ret = STree[p]->order_of_key(make_pair(v, 0));
        //if(ret == STree[p]->size()) ret = 0;
        return ret;
    }
    int mid = (l + r) / 2, ret = 0;
    if(ql <= mid)
        ret += askMin(p * 2, l, mid, ql, qr, v);
    if(qr > mid)
        ret += askMin(p * 2 + 1, mid + 1, r, ql, qr, v);
    return ret;
}
int askMax(int p, int l, int r, int ql, int qr, int v) {
    if(ql <= l && r <= qr) {
        int ret = STree[p]->order_of_key(make_pair(v, 2147483647));
        //if(ret == STree[p]->size()) ret = 0;
        return STree[p]->size() - ret;
    }
    int mid = (l + r) / 2, ret = 0;
    if(ql <= mid)
        ret += askMax(p * 2, l, mid, ql, qr, v);
    if(qr > mid)
        ret += askMax(p * 2 + 1, mid + 1, r, ql, qr, v);
    return ret;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &arr[i]);
        b[i] = arr[i];
        Insert(1, 1, n, i, b[i]);
    }
    Merge_Sort(1, n);
    printf("%d\n", ans);
    scanf("%d", &m);
    while(m--) {
        int l, r;
        scanf("%d %d", &l, &r);
        if(l > r) swap(l, r);
        //cout << askMax(1, 1, n, l + 1, r - 1, b[l]) << ' ' << askMin(1, 1, n, l + 1, r - 1, b[l]) << endl;
        //cout << askMin(1, 1, n, l + 1, r - 1, b[r]) << ' ' << askMax(1, 1, n, l + 1, r - 1, b[r]) << endl;
        ans += askMax(1, 1, n, l + 1, r - 1, b[l]) - askMin(1, 1, n, l + 1, r - 1, b[l]);
        ans += askMin(1, 1, n, l + 1, r - 1, b[r]) - askMax(1, 1, n, l + 1, r - 1, b[r]);
        if(b[l] > b[r])
            ans--;
        else if(b[l] < b[r])
            ans++;
        printf("%d\n", ans);
        Insert(1, 1, n, l, b[r]);
        Insert(1, 1, n, r, b[l]);
        Delete(1, 1, n, l, b[l]);
        Delete(1, 1, n, r, b[r]);
        swap(b[l], b[r]);
    }
    return 0;
}

未开O2优化，时间4.74s. 时间同样优于一些手写代码.

P2617 Dynamic Rankings

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> RbTree;
struct SegmentTree {
    int left, right;
    RbTree* Tree;
} STree[1000010];
int arr[1000010], cnt = 0;
void build(int p, int l, int r) {
    STree[p].left = l, STree[p].right = r;
    STree[p].Tree = new RbTree;
    for(int i = l; i <= r; ++i) {
        STree[p].Tree->insert(make_pair(arr[i], ++cnt));
    }
    if(l != r) {
        int mid = (STree[p].left + STree[p].right) >> 1;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
    }
    return;
}
void modify(int p, int place, int value) {
    STree[p].Tree->erase(STree[p].Tree->lower_bound(make_pair(arr[place], 0)));
    STree[p].Tree->insert(make_pair(value, ++cnt));
    if(STree[p].left == STree[p].right) {
        return;
    }
    int mid = (STree[p].left + STree[p].right) >> 1;
    if(place <= mid)
        modify(p * 2, place, value);
    else
        modify(p * 2 + 1, place, value);
    return;
}
int askRank(int p, int l, int r, int k) {
    if(STree[p].left > r || STree[p].right < l)
        return 0;
    if(STree[p].left >= l && STree[p].right <= r)
        return STree[p].Tree->order_of_key(make_pair(k, 0));
    return askRank(p * 2, l, r, k) + askRank(p * 2 + 1, l, r, k);
}
inline int askNum(int u, int v, int k){
    int l = 0, r = 1e9;
    while(l < r) {
        int mid = (l + r + 1) >> 1;
        if(askRank(1, u, v, mid) < k)
            l = mid;
        else
            r = mid - 1;
    }
    return r;
}
signed main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &arr[i]);
    }
    build(1, 1, n);
    for(int i = 1; i <= m; ++i){
        char opt;
        int a, b, c;
        while(isspace(opt = getchar()));
        scanf("%d %d", &a, &b);
        switch(opt){
            case 'Q':
                scanf("%d", &c);
                printf("%d\n", askNum(a, b, c));
                break;
            case 'C':
                modify(1, a, b);
                arr[a] = b;
                break;
        }
    }
    return 0;
}

开O2优化，进行了一些卡常.

静态区间第k小问题

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> RbTree;
struct SegmentTree {
    int left, right;
    RbTree Tree;
} STree[800020];
int arr[800020], cnt = 0;
void build(int p, int l, int r) {
    STree[p].left = l, STree[p].right = r;
    for(int i = l; i <= r; ++i) {
        STree[p].Tree.insert(make_pair(arr[i], ++cnt));
    }
    if(l != r) {
        int mid = (STree[p].left + STree[p].right) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
    }
    return;
}
int askRank(int p, int l, int r, int k) {
    if(STree[p].left > r || STree[p].right < l)
        return 0;
    if(STree[p].left >= l && STree[p].right <= r)
        return STree[p].Tree.order_of_key(make_pair(k, 0));
    return askRank(p * 2, l, r, k) + askRank(p * 2 + 1, l, r, k);
}
inline int askNum(int u, int v, int k){
    int l = 0, r = 1e9;
    while(l < r) {
        int mid = (l + r + 1) / 2;
        if(askRank(1, u, v, mid) < k)
            l = mid;
        else
            r = mid - 1;
    }
    return r;
}
signed main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%d", arr + i);
    }
    build(1, 1, n);
    for(int i = 1, a, b, c; i <= m; ++i){
        scanf("%d %d %d", &a, &b, &c);
        printf("%d\n", askNum(a, b, c));
    }
    return 0;
}

0x07 平衡树效率测试

感谢@郑朝曦zzx友情提供各种平衡树写法及1号环境测试.

根据目前情况，NOI系列竞赛应该会开启O2优化.这意味着O2优化中优势代码在比赛中很可能占优势.

按照数据生成器生成50个数据，插入数据概率为查询的10倍.

在数据随机并不卡数据结构的情况下，我们使用不同的代码进行测试得到的结果：

0x08 1号环境测试

测试环境： Windows 10 + Lemon 评测

CPU型号：Intel(R) Core(TM) i5-8400 CPU @ 2.80GHz （6线程）

编译器：TDM-GCC 4.9.2

不开O2优化的情况下：

此时Treap最快，其次是FHQ_treap，第三是pbds rb_tree_tag.

在去除读写干扰的情况下，pbds rb_tree_tag时间约为FHQ_Treap的1.2倍，为Treap的1.8倍.

开启O2优化的情况下：

此时pbds rb_tree_tag最快，Treap其次，FHQ_Treap第三.

在去除读写干扰的情况下，pbds rb_tree_tag时间约为FHQ_Treap的0.7倍，为Treap的0.75倍.

0x09 2号环境测试

测试环境：Windows 11 + Lemon

CPU型号：Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz （12线程）

编译器：TDM-GCC 10.3.0

下文为对时间分析不再赘述.

不开O2优化的情况下：

开O2优化的情况下：

0x0A 3号环境测试

测试环境：洛谷评测机 C++14（GCC 9）

测试题目：https://www.luogu.com.cn/problem/U272322

目前还是不公布测试结果了，大家可以自己测测看.

总结：在开O2优化的情况下，rb_tree_tag最快，且运行时间约为不开O2优化的0.5倍，快于所有手写的平衡树算法.

0x13 Trie树

字典树，英文名 trie.顾名思义，就是一个像字典一样的树.^{[12]}

可以发现，这棵字典树用边来代表字母，而从根结点到树上某一结点的路径就代表了一个字符串.

它的应用包括但不限于：

• 检索字符串

• AC 自动机

• 维护异或极值

• 维护异或和

定义：

__gnu_pbds::trie<Key, Mapped, 
    _ATraits =  __gnu_pbds::default_trie_access_traits<Key>::type,
    Tag = __gnu_pbds::pat_trie_tag,
    Node_Update = __gnu_pbds::null_node_update,
    _Alloc = std::allocator<char> >

Key表示存储的元素类型，肯定是string，对吧？

Mapped同平衡树，我们把它设为__gnu_pbds::null_type.

Tag决定底层的实现方式，目前只有__gnu_pbds::pat_trie_tag合法，它表示一个底层PATRICIA trie（检索字母数字编码信息的实用算法，Practical Algorithm To Retrieve Information Coded In Alphanumeric）.这种trie变体可以压缩使用空间.^{[14]}

这是官方文档对此的介绍^{[13]}：

(PATRICIA) trie 类似于树，但有以下区别：

它明确地将键视为一系列元素。 例如，trie 可以将字符串视为字符序列； trie 可以将数字视为位序列。

它不必二进制。 每个节点都有 n + 1 个扇出，其中 n 是不同元素的数量。

它仅在叶节点存储值。

内部节点具有以下属性：

• 每个都至少有两个子节点，

• 每个节点都与其任何后代共享相同的前缀。

(PATRICIA) trie 有一些有用的属性：

它可以配置为使用大型节点输出，从而提供非常高效的查找性能（尽管在插入复杂度和大小方面较劣）。

它适用于公共前缀键。

它可以支持有效的查询，例如哪些键匹配某个前缀。 这有时在文件系统和路由器中很有用。

所以本质上是一种压缩Trie，有更小的空间损耗，但是时间复杂度会高.

Node_Update：节点更新器.

• __gnu_pbds::null_node_update 空节点更新器

• __gnu_pbds::trie_prefix_search_node_update 前缀查找节点更新器，不使用这个就会无法前缀查找.

• __gnu_pbds::trie_order_statistics_node_update 顺序更新器，不使用这个无法进行顺序查找.

_Alloc：内存分配器.

操作：

• insert(x) 插入字符串x.

• erase(x) 删除字符串x.

• join(x) 将trie树x并入.

下面的例子是trie树的常规操作（查找字符串）^{[15]}：

//省略版权披露

/**
 * @file trie_prefix_search_example.cpp
 * An example showing how to use a trie for searching
 *    for words with a given prefix.
 */

/**
 * This example shows how to use a PATRICIA trie for searching
 * for words with a given prefix.
 */

#include <cassert>
#include <iostream>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>

using namespace std;
using namespace __gnu_pbds;

// A PATRICIA trie with a prefix-search node-updator type. Note that
// since the node updator is trie_prefix_search_node_update, then the
// container includes its method prefix_range.
typedef null_type        mapped_type;
typedef trie_string_access_traits<>     cmp_fn;
typedef pat_trie_tag             tag_type;

typedef trie<string, mapped_type, cmp_fn, tag_type, 
            trie_prefix_search_node_update> trie_type;

// The following helper function takes a trie object and r_key, a
// const reference to a string, and prints all entries whose key
// includes r_key as a prefix.
void
print_prefix_match(const trie_type& t, const string& key)
{
    typedef trie_type::const_iterator         const_iterator;
    typedef pair<const_iterator, const_iterator>     pair_type;

    cout << "All keys whose prefix matches \"" << key << "\":" << endl;

    const pair_type match_range = t.prefix_range(key);
    for (const_iterator it = match_range.first; it != match_range.second; ++it)
    cout << *it << ' ';
    cout << endl;
}

int main()
{
    trie_type t;

    // Insert some entries.
    assert(t.insert("I").second == true);
    assert(t.insert("wish").second == true);
    assert(t.insert("that").second == true);
    assert(t.insert("I").second == false);
    assert(t.insert("could").second == true);
    assert(t.insert("ever").second == true);
    assert(t.insert("see").second == true);
    assert(t.insert("a").second == true);
    assert(t.insert("poem").second == true);
    assert(t.insert("lovely").second == true);
    assert(t.insert("as").second == true);
    assert(t.insert("a").second == false);
    assert(t.insert("trie").second == true);

    // Now search for prefixes.
    print_prefix_match(t, "");
    print_prefix_match(t, "a");
    print_prefix_match(t, "as");
    print_prefix_match(t, "ad");
    print_prefix_match(t, "t");
    print_prefix_match(t, "tr");
    print_prefix_match(t, "trie");
    print_prefix_match(t, "zzz");
    return 0;
}

在main()函数第一部分，插入了很多字符串.一旦字符串重复，那么其返回值的second成员为false，由此可以判定字符串是否重复.

当然，如果想要删除，可以erase其first迭代器成员.

print_prefix_match(trie, x)函数查找前缀为x的字符串.其函数就是通过prefix_range(x)查找前缀为x的字符串的左右迭代器，并进行遍历.

P8306 【模板】字典树

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){ if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
char buffer[3000005];
signed main(){
    int T = read();
    while(T--){
        __gnu_pbds::trie<string, __gnu_pbds::null_type, __gnu_pbds::trie_string_access_traits<>,
                    __gnu_pbds::pat_trie_tag, __gnu_pbds::trie_prefix_search_node_update> trie;
        int n = read(), q = read();
        for(int i = 1; i <= n; i++){
            scanf("%s", buffer);
            trie.insert(string(buffer));
        }
        while(q--){
            int ans = 0;
            scanf("%s", buffer);
            auto range = trie.prefix_range(string(buffer));
            for(auto it = range.first; it != range.second; it++) ans++;
            printf("%d\n", ans);
        }
    }
    return 0;
}

遗憾的是，这道题只能拿32pts的暴力分.其他分数需要手写字典树才能拿到，这就是为什么没有人用__gnu_pbds::trie的原因.

值得一提的是，如果你的__gnu_pbds::trie无法运行，请关闭你的一些编译选项，或在洛谷IDE下使用.^{[17]}

P2580 于是他错误的点名开始了

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
using namespace std;
__gnu_pbds::trie<string, int> trie;
signed main(){
    int n, m;
    string str;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        cin >> str;
        trie[str] = 1;
    }
    scanf("%d", &m);
    for(int i = 1; i <= m; i++){
        cin >> str;
        auto result = trie.find(str);
        if(result == trie.end()){
            printf("WRONG\n");
        }else if(result->second == 1){
            printf("OK\n");
            result->second++;
        }else{
            printf("REPEAT\n");
            result->second++;
        }
    }
    return 0;
}

这里展示了__gnu_pbds::trie类似std::map的用法，即映射.

0x14 堆

堆是一棵树，其每个节点都有一个键值，且每个节点的键值都大于等于/小于等于其父亲的键值.

每个节点的键值都大于等于其父亲键值的堆叫做小根堆，否则叫做大根堆.STL 中的 priority_queue 其实就是一个大根堆.^{[7]}

定义：

    __gnu_pbds::priority_queue<T, Compare = std::less<T>, Tag = __gnu_pbds::pairing_heap_tag, Allocator = std::allocator<char> >

T表示存储的元素类型.

Compare表示比较类型，可以是less<T>（大根堆）或greater<T>（小根堆）.

Tag共有5种，分别是：

• __gnu_pbds::pairing_heap_tag 配对堆，在非原生元素中，该堆表现最好.

• __gnu_pbds::binary_heap_tag 二叉堆，在原生元素中，该堆表现最好.

• __gnu_pbds::binomial_heap_tag 二项堆（即二项队列），合并操作优于二叉堆，查询操作劣于二叉堆

• __gnu_pbds::rc_binomial_heap_tag 冗余计数二项堆

• __gnu_pbds::thin_heap_tag 除合并操作外与斐波那契堆一致

• __gnu_pbds::Allocator 内存分配器，同上

引用自官方文档^{[8]}的简要翻译（甚至比我说得明白）：

实现

优先队列有三种实现方式：第一种使用二叉堆，通常使用序列； 第二个使用一棵树（或树的森林），它通常不如关联容器的树结构化（译者注：即二项堆等）；第三个简单地使用关联容器. 这些分别显示在上图 A1，A2，B，C 中.

粗略地说，任何从优先队列中push和pop的值都必须产生对数开销（译者注：即\Theta(\log(n))的时间复杂度）.任何可以避免这种情况的优先队列实现都将违反基于比较的排序的已知界限.

大多数实现在push和pop操作的渐近时间复杂度方面没有区别，但它们在所涉及的常量、其他操作（例如：修改）的复杂性以及单个操作的最坏情况复杂性方面有所不同。 通常，实现越“结构化”（即，它拥有的内部不变量越多），其push和pop操作的时间复杂度就越高.

pb_ds 使用单个类实现不同的算法：__gnu_pbds::priority_queue。 实例化 Tag 模板参数如下：

• Tag = binary_heap_tag： 创建一个形式为上图 A1 或 A2的二叉堆. 如果 Value_Type 由原生类型实例化，则使用上图 A1； 否则使用上图 A2. 这种实现相对非结构化，因此具有良好的push和pop性能； 它是原生的“同类最佳”. 相反，它具有较高的最坏情况性能，并且只能支持线性时间的modify和erase操作.

• Instantiating Tag = pairing_heap_tag 创建上图 B 中形式的配对堆.这种实现也相对非结构化，因此具有良好的push和pop性能； 它是非原生类型的“同类最佳”. 它还具有非常好的最坏情况push和join性能（O(1)），但具有很高的最坏情况pop复杂度.

• Instantiating Tag = binomial_heap_tag 创建上图 B 中形式的二项堆。这种实现比配对堆更具结构化，因此push和pop性能更差. 相反，它对 pop 具有亚线性的最坏情况界限，例如，因此在响应性很重要的情况下，它可能是首选.

• Instantiating Tag = rc_binomial_heap_tag 创建上图 B 中形式的二项堆，并伴随有一个管理树的冗余计数器（即冗余计数二项堆）. 因此，这种实现比二项式堆更具结构化，因此push和pop性能更差. 相反，它保证了 O(1) 的push复杂性，因此在二项式堆的响应能力不足的情况下，它可能是首选.

• Instantiating Tag = thin_heap_tag 创建上图 B 中形式的薄堆（即thin heap，译者注）。这种实现也比配对堆更具结构化，因此push和pop性能更差. 相反，它比斐波那契堆具有更好的最坏情况和相同的时间复杂度，因此可能更适合某些图算法.

当然，可以使用任何保持顺序的关联容器作为优先队列，如上图 C 所示，可能通过在关联容器上创建一个适配器类（就像 std::priority_queue 可以适应 std::vector）.这样做的好处是根本不需要交叉引用. 优先队列本身是一个关联容器。 大多数关联容器的结构过于结构化，无法在推送和弹出性能方面与优先级队列竞争.

编者：下标可能与Wikipedia有所冲突，优先考虑下表.

摊销的推送和弹出操作

在许多情况下，优先队列主要用于push和pop序列。所有底层数据结构都具有相同的对数复杂度（即\Theta(\log(n))），但它们在常数方面有所不同.

上表表明，不同的数据结构在某些方面是“受约束的”.一般来说，如果一个数据结构的最坏情况复杂度比另一个低，那么它在摊销的意义上会执行得更慢。因此，例如，冗余计数器二项堆（priority_queue with Tag = rc_binomial_heap_tag）比二项堆（priority_queue with Tag = binomial_heap_tag）具有更低的最坏情况推送性能，因此它的摊销推送性能在常量方面更慢.

如表所示，“约束最少”的底层数据结构是二叉堆和配对堆。因此，它们在摊销常数方面表现最好也就不足为奇了.

配对堆似乎对非原生类型（例如 std::string）表现最好，二进制堆似乎对原始类型（例如int）表现最好.

图论算法

在某些图论算法中，需要decrease-key操作（译者注：将该节点改变权值，相当于修改操作，我们使用先弹出再加入判vis的方式实现，见《算法导论》）；如果值增加，此操作与修改相同.

这使得很难决定在这种情况下使用哪种实现。例如，Dijkstra 的最短路径算法需要 \Theta(n) 的 push 和 pop 操作（在顶点的数量上），但是 O(n^2) 的修改操作，在实践中也可以是 \Theta(n). 很难找到图的先验特征，其中修改操作的实际数量将超过推送和弹出操作的数量.

例如堆优化Dijkstra算法，其时间函数为^{[35]}

设图中的节点数为n，边个数为m，平均每个点的边数k = \frac{m}n.

对于std::priority_queue，__gnu_pbds::pairing_heap_tag以及__gnu_pbds::binary_heap_tag,其为：

对于__gnu_pbds::binomial_heap_tag和__gnu_pbds::rc_binomial_heap_tag，其为：

对于__gnu_pbds::thin_heap_tag（优化的斐波那契堆），其为：

很显然，正如上文所说，对于一些图论算法，__gnu_pbds::thin_heap_tag表现地更好. 那么是不是这样呢？

对于P4779 【模板】单源最短路径（标准版）,作者得到了以下结果（同一时间段内）：

最后发现，在没有开优化的情况下，是pbds所带配对堆好用. 开优化的情况下，是STL的优先队列好用.

至于自带的thin_heap_tag，由于封装过于严密，常数很大，并没有体现出时间复杂度优势来.

Wikipedia对于时间复杂度的解释^{[9]}：

所以我们得出一个结论：

• 当数据类型为原生类型（如char或int）时，推荐使用__gnu_pbds:: binary_heap_tag.

• 当数据类型为非原生类型（如string或pair）时，推荐使用__gnu_pbds::pairing_heap_tag.

举个例子：

__gnu_pbds::priority_queue<pair<int, int>> //大根堆
__gnu_pbds::priority_queue<pair<int, int>, std::greater<pair<int, int> > > //小根堆
__gnu_pbds::priority_queue<int, std::greater<int>, __gnu_pbds::binary_heap_tag> //小根堆，原生类型

操作：

• push(x) 在堆中插入元素x.

• pop() 弹出堆顶元素.

• top() 返回堆顶元素

• empty()/size() 返回是否为空/大小

• modify(iterator, key) 修改迭代器位置的值

• erase(iterator) 删除迭代器位置值

• join(other) 把other合并到原堆并清空other

P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
int n, t[10010];
__gnu_pbds::priority_queue<int, greater<int> > heap;
int main() {
    cin >> n;
    for(int i = 0; i < n; i++) {
        cin >> t[i];
        heap.push(t[i]);
    }
    int ans = 0;
    while(heap.size() > 1) {
        int a = heap.top();
        heap.pop();
        int b = heap.top();
        heap.pop();
        ans += a + b;
        heap.push(a + b);
    }
    cout << ans << endl;
    return 0;
}

P3377 【模板】左偏树（可并堆）

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef __gnu_pbds::priority_queue<pair<int, int>, greater<pair<int, int> >, pairing_heap_tag> Pqueue;
Pqueue q[1000005];
int father[1000005], cnt[1000005];
int findx(int x){
    if(father[x] != x) return father[x] = findx(father[x]);
    return x;
}
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++) father[i] = i;
    for(int i = 1, t; i <= n; i++){
        scanf("%d", &t);
        q[i].push(make_pair(t, i));
        cnt[i]++;
    }
    while(m--){
        int op, x, y, ix, iy;
        scanf("%d", &op);
        if(op == 1){
            scanf("%d %d", &x, &y);
            ix = findx(x), iy = findx(y);
            if(!cnt[x] || !cnt[y] || ix == iy) continue;
            q[ix].join(q[iy]);
            father[iy] = father[ix];
        }else{
            scanf("%d", &x);
            ix = findx(x);
            if(!cnt[x] || q[ix].empty()) {printf("-1\n"); continue;}
            printf("%d\n", q[ix].top().first);
            cnt[q[ix].top().second]--;
            q[ix].pop();
        }
    }
    return 0;
}

注意到配对堆的插入与合并时间复杂度均为O(1)，所以可以利用这种数据结构完成可并堆.

注意-1不好判断，注意看条件.

0x15 进阶教程

本节内容有些超过范围了，其实用处不大.

0x16 __gnu_pbds::tree 的遍历

通过__gnu_pbds::tree::node_begin()获取树根的node_iterator迭代，然后通过__gnu_pbds::tree::node_iterator::get_l_child()与node_iterator::get_r_child()获取其左右孩子，进行递归遍历. ^{[26]}

node_iterator重载了解引用运算符，用于访问其值（一个__gnu_pbds::container_base::iterator对象^{[27]}），然后再对其解引用，就可以得到原值. ^{[28]}

当一个节点没有左/右儿子时，__gnu_pbds::trie::node_iterator::get_l_child()/__gnu_pbds::trie::node_iterator::get_r_child()将返回tree::node_end()的值.此时递归过程可以终止. ^{[29]}

特别地，如果映射类型不为__gnu_pbds::null_type，则对迭代器进行两次解引用的对象是一个pair<T1, T2>，其中T1表示原始类型，T2表示映射类型.

下面是一个中序遍历的例子：

P1177 【模板】快速排序

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace std;
typedef __gnu_pbds::tree<pair<int, int>, __gnu_pbds::null_type> Tree;
Tree tree;
void solve(Tree::node_iterator it){ //中序遍历
    Tree::node_iterator left = it.get_l_child(), right = it.get_r_child();
    if(left != tree.node_end()) solve(left);
    cout << (*it)->first << ' ';
    if(right != tree.node_end()) solve(right);
}
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 1, t; i <= n; i++){
        scanf("%d", &t);
        tree.insert(make_pair(t, i));
    }
    solve(tree.node_begin());
    return 0;
}

0x17 __gnu_pbds::trie的遍历

下文摘自官方资料^{[30]}：

元素访问特征

Trie 本质上将其键视为元素序列. 例如，trie 可以将字符串视为字符序列. 一个 trie 需要将 n 个元素中的每一个映射到 [0, n - 1] 中的一个数字。例如，trie 可以将字符 c 映射到 static_cast<size_t>(c)（译者注：即强制转换为一个数字）.

看起来，trie 可以假设它的键支持常量迭代器，并且这个迭代器的 value_type 可以转换为 size_t.但是，有几个原因可以将 trie 访问其键元素的机制与 trie 分离：

• 在某些情况下，元素的数值是不合适的.考虑一个存储 DNA 字符串的树。使用扇出最大为 5 = 1 + |{'A', 'C', 'G', 'T'}| 的 trie 是合乎逻辑的。不过，这需要将'T'映射到 3。

• 在某些情况下，键的迭代器与所需的不同。例如，通过使用字符串的 reverse_iterator，可以使用 trie 搜索常见的后缀。再举一个例子，如果每个节点都在一个 UNICODE 字符上分支，则映射 UNICODE 字符串的 trie 将有一个巨大的扇出；相反，可以定义一个迭代 8 位（或更少）组的迭代器。

编者注：“扇出”此处应该指转移边的最大数目，相当于trie数组的第二维^{[36]}

因此，trie 由 E_Access_Traits 参数化——指示如何访问序列元素的特征。 string_trie_e_access_traits 是字符串的特征类。每个这样的特征都定义了一些类型，例如，

typename E_Access_Traits::const_iterator

是一个迭代键元素的常量迭代器。特征类还必须定义用于获取键的第一个和最后一个元素的迭代器的方法。

下图 显示了一个 (PATRICIA) trie，它是通过插入以下词语产生的：“我希望我能看到一首像 trie 一样可爱的诗”（不幸的是，它不押韵）。

叶节点包含值；每个内部节点包含两个 typename E_Access_Traits::const_iterator 对象，表示子树中所有键的最大公共前缀。例如，带阴影的内部节点以具有叶子a和as的子树为根。最大公共前缀是a。因此，内部节点包含常量迭代器，一个指向a，另一个指向s。

使用__gnu_pbds::trie::node_begin()可以获得树根节点的迭代器.

对一个叶子节点的迭代器，进行解引用可以获得一个__gnu_pbds::container_base::iterator对象，对该对象进行解引用得到一个字符串，如上图.（这和我查阅到的官方资料有所出入）

对一个节点迭代器，有__gnu_pbds::trie::node_iterator::num_children()方法.这个方法返回改节点的孩子个数，令其返回值为x，则孩子的编号为[0, x)的一个区间.

特别地，若其返回零，那么这个迭代器为叶子节点，此时可以读取节点的值.

下面是对上图所展示的trie树进行深度优先搜索的过程.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
using namespace std;
typedef __gnu_pbds::trie<string, __gnu_pbds::null_type> Trie;
Trie trie;
int cnt = 0;
void solve(Trie::node_iterator it){
    if(it.num_children() == 0){
        printf("%s\n", (*it)->c_str());
    }
    for(int i = 0; i < it.num_children(); i++){
        solve(it.get_child(i));
    }
}
int main(){
    trie.insert("I");
    trie.insert("wish");
    trie.insert("that");
    trie.insert("I");
    trie.insert("could");
    trie.insert("ever");
    trie.insert("see");
    trie.insert("a");
    trie.insert("poem");
    trie.insert("lovely");
    trie.insert("as");
    trie.insert("a");
    trie.insert("trie");
    solve(trie.node_begin());
    return 0;
}

0x18 堆

引自官方资料^{[31]}：

有许多不同的底层数据结构用于实现优先队列.不幸的是，大多数此类结构都旨在使 push 和 top 高效，因此不允许有效访问其他元素：例如，它们不支持有效的 find 方法。在使用任意值访问和“做某事”都很重要的用例中，一个人会不走运.例如，许多图论算法需要修改一个值.

为了访问和操作优先级队列中的任意值，需要从某种形式的关联容器中引用优先级队列的内部结构——这是不可避免的.当然，为了保持对优先级队列的封装，这需要以最小化暴露于实现内部的方式来完成.

在 pb_ds 中，优先级队列的 insert 方法返回一个迭代器，如果有效，它可以用于后续的修改和擦除操作.这既保留了优先级队列的封装，又允许访问任意值（因为从推送操作返回的迭代器可以存储在某种形式的关联容器中）.

优先级队列的迭代器在其失效保证方面存在问题。假设在迭代器上调用 operator++ 会将其与“下一个”值相关联。优先级队列是自组织的：每个操作都会改变“下一个”值的含义。因此，push 将返回一个可以递增的迭代器是没有意义的——这不可能有任何用处。此外，与基于散列的容器的情况一样，定义后续推送操作是否使先前返回的迭代器无效是很尴尬的：它使它无效，因为它的“下一个”值与其先前认为的值无关它的“下一个”值。但是，它可能不会使其无效，因为它可以被取消引用并用于修改和擦除操作。

与其他无序关联容器的情况类似，pb_ds 使用点类型和范围类型迭代器之间的区别。优先级队列的迭代器始终可以转换为 point_iterator，而 const_iterator 始终可以转换为 const_point_iterator。

应该注意，替代设计可以将关联容器嵌入优先级队列中。可以，但很可能不应该。首先，应该注意的是，总是可以封装一个优先级队列和一个关联容器映射值到优先级队列迭代器，而不会造成性能损失。但是，不能“取消封装”嵌入关联容器的优先级队列，这可能会导致性能损失。假设需要将每个值与一些与优先级队列无关的数据相关联。然后使用 pb_ds 的设计，可以使用关联容器将每个值映射到由该数据和优先级队列的迭代器组成的对。使用嵌入式方法需要使用两个关联容器。在一个值可以同时驻留在许多优先级队列中的情况下，可能会出现类似的问题。

// 定义一个堆
__gnu_pbds::priority_queue<int, __gnu_pbds::null_type> p;

// 在堆里插入一些元素……
priority_queue<int>::point_iterator it = p.push(0);

p.push(1);
p.push(2);

// 修改迭代器指向的值
p.modify(it, 3);

assert(p.top() == 3);

0x19 手写节点更新器

0x1A 手写__gnu_pbds::tree的节点更新器

上文说到，平衡树本质上是一个尽量维持平衡的二叉搜索树，所以在不关心平衡树具体实现的情况下，可以把平衡树当成普通的二叉搜索树.

如上图^{[32]}，我们在定义一个__gnu_pbds::tree的时候，提供了一个节点更新器类型（见上文）.

该类型的定义如下：

//为了好记，作者进行了名称优化
template<typename const_node_iterator, typename node_iterator, typename cmp, typename alloc>
struct customize_node_update{
    typedef customize_type metadata_type;
    void operator()(node_iterator it, const_node_iterator end_it){
        //...
    }
};

首先，一个节点更新器的模板应为template<typename const_node_iterator, typename node_iterator, typename cmp, typename alloc>. 当然，这些类型名称使用别的也是没问题的.只是注意模板定义与函数参数的常变量顺序相反.

模板参数依次为：常量迭代器，迭代器。比较器，分配器.

customize_node_update::metadata_type是一个自定义类型，表示使用的元数据.（比如标记一类的东西，这些东西不属于原数据，是一种辅助记录的工具）

当需要更新节点x时，会调用customize_node_update(it_x, __gnu_pbds::tree::node_end()).

customize_node_update::operator()的第一个参数表示当前更新的节点，这个节点还没有被更新到，亟待更新. 第二个参数表示一个无效值，如上节所述，如果一个节点没有左/右孩子，那么调用对应函数返回其值.

所以迭代器的使用同上节，我们就可以把这个树的所有节点带上一个元数据了.

为了访问整棵树，我们需要设置两个虚成员函数. 如下述：

virtual const_node_iterator node_begin() const=0;
virtual const_node_iterator node_end() const=0;

其中我们设定了两个纯虚函数用于得到其基类的函数，=0表示这个函数是一个纯虚的函数，然后我们调用它们就相当于调用原先自带的函数（你也可以重定义它们）.

这样我们就可以在这个类里使用到__gnu_pbds::tree::node_begin()/__gnu_pbds::tree::node_end()了.结合上节树的遍历，我们就可以任意修改使用这棵平衡树了.

当然，如果你在节点更新器里定义成员函数。就可以通过__gnu_pbds::tree直接访问.

通过node_iterator::get_metadata()可以得到元数据.

通过const_cast<metadata_type&>(it.get_metadata()) = xxx; 可以实现元数据写入.

关于此例，请看参考文献3的相关介绍. 过于复杂，本文不再介绍.

通过这种方法，可以使用__gnu_pbds::tree来定义线段树. ^{[34]}

0x1B rope库

0x1C 简介

__gnu_cxx::rope是一种可持久化数据结构.^{[19]}

它支持字符串的插入、添加等操作，不建议使用单个字符的操作.^{[20]}

换言之，__gnu_cxx::rope适合大量、冗长的串操作，而不是单点操作. 对于区间最大值之类问题貌似无能为力.

比如赋值、串联和子串的操作所花的时间差不多不依赖字符串的长度。与C的字符 串不同，rope是超长字符串的一个合理的表现，比如编辑缓冲区或邮件信息. 在后端，rope被实现为引用计数子串的树，而且每个子串都存储为字符数组。rope 接口的一个有趣方面是begin和end成员函数总是返回const_iterator.这是为了阻止用户进行改变单个字符的操作。这样的操作是昂贵的，rope针对涉及整个字符串 的动作（如上所述，例如，赋值、串联和获取子串）优化；单个字符操作表现很差. ^{[21]}

尽管rope可以被视为字符的容器，并且几乎是序列，但这很少是完成任务的最有效方式。 替换绳索中的单个字符很慢：每个字符替换基本上由两个子字符串操作和两个连接操作组成。 绳索主要针对功能性更强的编程风格。在 10 兆字节的绳索中间插入一个字符应该花费大约 10 微秒的时间，即使保留了原始的副本，例如 作为编辑历史的一部分。可以将生成字符的函数视为绳索。 因此，一根绳子可能是一个 100MByte 的文件，只有在检查字符串的该部分时才能读取该文件。 将字符串连接到此类文件的末尾不涉及读取文件。 ^{[22]}

读完这些，读者应该明白了.__gnu_cxx::rope专用于暴力一些长串并快速处理，其时间几乎和串长度没有关系.所以遇到一些区间操作的题可以用这个数据结构暴力.

0x1D 定义

__gnu_cxx::rope是定义在__gnu_cxx命名空间的一个扩展.自然，可以类比pb_ds库的使用.

#include <ext/rope>
__gnu_cxx::rope<char> rope1;
__gnu_cxx::rope<int> rope2;

0x1E 使用

__gnu_cxx::rope库的使用相比pb_ds来讲非常简单.^{[23]}

下列的时间复杂度（除单点操作外）为\Theta(n\sqrt n).

空间复杂度很小，根据上述参考资料猜测为\Omega(\sqrt n).

__gnu_cxx::rope重载了各种运算符，包括以下几种：

• operator+()与operator+=()，拼接运算符

• operator-()与operator-=()，剪切运算符

• operator<()与operator==()，比较运算符

• operator[](int x)，取出rope下标为x的值

__gnu_cxx::rope还有一些常用的方法，其中类型T表示定义类型（可以为常用的char或int来维护不同的东西）.

• insert(int pos, T* s, int n) 将数组s中下标区间在[0, n)中的所有值插入rope的下标pos处.

• append(T* s, int pos, int n) 将数组s中下标区间在[pos, pos + n)的所有值连接到rope结尾. 特别地，append(x)相当于vector中的push_back(x)，即直接在结尾加上x.

• substr(int pos, int len) 提取rope下标区间在[pos, pos + len)的值，注意与substr(begin, end)的迭代器用法区分，这个用法表示提取下标区间在[begin,end)的值.

• erase(int pos, int num) 删除rope下标区间在[pos, pos + num)的值

• copy(int pos, int len, T* s) 将rope中下标区间在[pos, pos + len)的值复制到数组s之中.

• replace(int pos, int n, T* x) 将rope中下标区间在[pos, pos + n)的元素替换成x中的元素（上面那个的反操作）

如果需要翻转一段区间，可以维护一正一反的rope，然后交换区间就可以了.

P3919 【模板】可持久化线段树 1（可持久化数组）

#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
__gnu_cxx::rope<int> *histories[1000005];
int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    histories[0] = new __gnu_cxx::rope<int>();
    histories[0]->append(0);
    for(int i = 1, t; i <= n; i++){
        scanf("%d", &t);
        histories[0]->append(t);
    }
    for(int v = 1; v <= m; v++){
        int version, opt, loc;
        scanf("%d %d %d", &version, &opt, &loc);
        histories[v] = new __gnu_cxx::rope<int>(*(histories[version]));
        if(opt == 1){
            int value;
            scanf("%d", &value);
            histories[v]->mutable_reference_at(loc) = value;
        }else{
            printf("%d\n", histories[v]->at(loc));
        }
    }
    return 0;
}

这道题使用__gnu_cxx::rope解的话只能拿到64pts，剩下的分数是MLE.

虽然很大程度上__gnu_cxx::rope的空间消耗可以忽略，但是在数据量极大（甚至下载不下来，如这道题）的情况下还是要注意注意的.

P3391 【模板】文艺平衡树

#include <bits/stdc++.h>
#include <ext/rope>
using namespace std;
__gnu_cxx::rope<int> A, B;
int n, m;
int main(){
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= n; i++){
        A.append(i), B.append(n - i + 1);
    }
    while(m--){
        int l, r;
        scanf("%d %d", &l, &r);
        l--, r--;
        r++;
        __gnu_cxx::rope<int> tmp = A.substr(l + A.begin(), r + A.begin());
        A = A.substr(0 + A.begin(), l + A.begin()) + B.substr(n - r + B.begin(), n - l + B.begin()) + A.substr(r + A.begin(), n + A.begin());
        B = B.substr(0 + B.begin(), n - r + B.begin()) + tmp + B.substr(n - l + B.begin(), n + B.begin());
    }
    for(int i = 0; i < n; i++){
        printf("%d ", A[i]);
    }
    return 0;
}

这就是之前我们提到的用法，记住要把substr()的普通用法和迭代器用法分开，万万不可混用！

这道题可以拿到100pts.

时间差距极小！

0x1F STL库

官方自带的STL库中就有很多方便的函数，可以供我们使用。^{[25]}

一些常用的函数就略去了，这些大家都应该知道.

作者喜欢使用万能头，并且其实不是很常用这些函数.

0x20 最大值/最小值函数

0x21 min()与max()的列表版本

普通的min()与max()只能得到两个数的最值，但是这个版本可以得到许多数的最值.

例子：

min({1, 2, 3, 4, 5});
max({5, 4, 3, 2, 1});

时间复杂度：\Theta(n).

0x22 minmax_element(begin, end)

这个函数用于查询区间[begin, end)的最大、最小值，返回一个pair，first最小，second最大.

时间复杂度\Theta(n).

0x23 数列类函数

0x24 shuffle(begin, end, gen) & is_sorted(begin, end)

这个函数可以随机打乱数组，其中gen是一个随机数生成器（一般为mt19937），begin与end为首尾迭代器，时间复杂度\Theta(n).

is_sorted()可以检查一个序列是否有序，时间复杂度为\Theta(n).

利用这个函数，可以写成经典的随机化排序算法：

P1177 【模板】快速排序

#include <algorithm>
#include <iostream>
#include <random>
#include <type_traits>
#include <ctime>
using namespace std;
vector<int> arr;
int main(){
    int n;
    scanf("%d", &n);
    for(int i = 0, t; i < n; i++){
        scanf("%d", &t);
        arr.push_back(t);
    }
    int Min = *min_element(arr.begin(), arr.end());
    while(!(is_sorted(arr.begin(), arr.end()) && arr[0] == Min)){
        shuffle(arr.begin(), arr.end(), mt19937(time(NULL)));
    }
    for(int i = 0; i < n; i++){
        printf("%d ", arr[i]);
    }
    return 0;
}

这个程序对于这道题可以随机得20pts，但是在极其幸运的情况下可以得到100pts（真的有这种情况吗）

时间复杂度：最优 \Theta(n) 最劣 运行不出来

0x25 iota(begin, end, value)

将区间[begin, end)赋值为{value, value + 1, value + 2}等等.

时间复杂度为\Theta(n).

可以用来初始化并查集等.

0x26 prev_permutation(begin, end) & next_permutation(begin, end)

两个求排列的函数，一个求上一个排列，一个求下一个排列.

当然，“排列”存在相同元素也是可以的.

如果已经是第一个/最后一个排列，返回false，否则返回true，并将区间[begin, end)更改为上/下一个排列.

时间复杂度：\Theta(n)

0x27 count(begin, end, value) & count_if(begin, end, func) & replace(begin, end, value1, value2) & fill(begin, end, value) & copy(begin, end, begin2) & find(begin, end, value)

这六个函数都是区间赋值或检查类的，所以作者将其合并在一起.

这些函数的时间复杂度均为\Theta(n).

• count(begin, end, value) 返回区间[begin, end)中值为value的个数.

• count_if(begin, end, func) 对于区间[begin, end)中的一个值x，返回func(x)为true的个数. 其中func应为一个返回值为bool，有一个参数的函数指针，也可以是lambda函数.关于lambda函数，本文不再介绍.

• replace(begin, end, value1, value2) 将区间[begin, end)的所有等于value1的数替换为value2.

• fill(begin, end, value) 将区间[begin,end)全部设为value，类似函数memset.

• copy(begin, end, begin2) 将区间[begin,end)复制到区间[begin2,begin2+(end-begin)).

• find(begin, end, value) 线性查找区间[begin,end)中为value的数.对于有序区间，请使用lower_bound()或upper_bound().

0x28 accumulate(begin, end, value)

返回区间[bgein, end)中每一个元素加上初始值value的总和，即sum(begin, end) + value(end - begin).

时间复杂度为\Theta(n).

0x29 partial_sum(begin, end, begin2) & adjacent_difference(bg1,ed1,bg2)

• partial_sum(begin, end, begin2) 将区间[begin,end)的前缀和存储至[begin2, begin2+(end-begin))中.

• adjacent_difference(bg1,ed1,bg2) 将区间[begin,end)的差分存储至[begin2, begin2+(end-begin))中.

时间复杂度为\Theta(n).

0x2A inplace_merge(begin, mid, end)

对区间[begin, mid)和区间[mid, end)进行归并排序，并存入区间[begin, mid).

时空复杂度均为\Theta(n). 可以传入第四个参数作为比较.

0x2B 其它

0x2C function<>

function<R<T1, T2, ..., Tn> > f;表示定义一个返回值类型为R，形参为T1, T2, ..., Tn的名为f的函数.

function<int<int, int> > func = [](int a, int b)->int{
    return a + b;
}

显然，我们做到了在C++里像JavaScript一样使用lambda函数了！

在这个类型出来之前，我们一般使用auto关键字（我也喜欢这样使用）：

auto func = [](int a, int b)->int{
    return a + b;
}

同样地，function<>也可以作为函数指针，如下例：

int a(int a, int b){
    return a + b;
}
function<int<int, int> > func = a;
//其等价于
int(func*)(int, int) a;

0x2D Q&A

0x2E pbds带的平衡树不能支持重复元素吗

是的. 二叉搜索树在处理数据时有的将重复数据忽略，或者记录一个计数器来存储到底有几个一样的数据. pbds平衡树使用前一种方式解决问题，这就使得无法处理重复元素.

然而，可以使用pair存储方式来去重，有两种方法：存一个不可重的顺序值，或存储数据出现了几次.

然而这样对性能有一定损耗.

0x2F 参考文献

感谢@郑朝曦zzx对这篇文章做的贡献！