【5.13 更新】超超超超超冷门的 9 个 C++ 自带数据结构

__CrossBow_EXE__ · 2025-05-07 14:06:58 · Algo. & Theory

前言

在我周围的 OI 圈里，流传着这样一张图：

这上面的 9 个 C++ 自带数据结构，都是非常冷门的。据我所知，我们学校根本没有使用其中 2 个的。

于是，我就撰写了这篇文章，来介绍这些数据结构。它们有的好用到爆，有的啥用没有。我给这 9 个数据结构的好用结构排了个名：

名称	好用程度（满分为 5）
`pb_ds` 哈希表	5
`pb_ds` 平衡树	5
`pb_ds rope`	4
`forward_list`	3
`pb_ds list_update`	3
`pb_ds trie`	2
`pb_ds` 优先队列	2
`array`	1
`vstring`	1

我会从下往上来介绍每个数据结构。

介绍

这部分会介绍上面提到的九个数据结构。

`vstring`

如果 vstring 说自己第二冷门，相信没有数据结构敢当第一。放眼全世界，有关 vstring 的讨论和介绍屈指可数。我只找到了两篇讨论帖子，一个是国外的，一个是国内的。这里我总结一下。

vstring 的头文件是 #include<ext/vstring.h>，可以在 C++11 及后面的版本使用。它是 GNU C++ 中 GNU libstdc++ 的一部分。据说它在 std::string 的实现中起到了重要作用。

vstring 可以优化实现字符串的过程。换句话说，vstring 是优化后的 string，在字符串扩展和内存分配方面吊打 string。如果出题人过于毒瘤，卡 string，那么我们可以用 vstring 卡常。

此外，它与 std::basic_string 兼容。也就是说它们可以互相转化。

如果你还想了解更多，可以参考 ext/vstring.h 头文件的源代码。

`array`

从这里开始，就肯定有人在用了。

array 基本和普通数组一样，但它不像 vector 一样可以伸缩。它依然需要 C++11 或以上才能用，使用时直接万能头即可。下面给出一些常用的操作。

operator[]：访问数组某一位的值，和普通数组一样。
front，back：分别是访问第一个和最后一个元素。
size，empty：功能都和其它 STL 一样。
fill：以指定值填充一个 array。与 memset 不同的是，fill 可以填充任意值，包括 1 等。
swap：交换两个 array。复杂度不是 O(1)，是 O(n)。

其余的遍历等操作和 vector 一样。

`pb_ds` 优先队列

这个优先队列和我们平常用的 priority_queue 名字一样，而且都用堆实现，但用法有一点不同。它的头文件是 ext/pb_ds/priority_queue.hpp。为了避免和 queue 中的优先队列重名，不要 using namespace __gnu_pbds;。

它的创建方法一般是 __gnu_pbds::priority_queue<T,greater<T>,tag> q;，其中 T 是数据类型，tag 是堆的类型。这个例子是小根堆，默认是大根堆。

它自带的堆的类型有 5 种。它们分别是：

__gnu_pbds::pairing_heap_tag，配对堆
__gnu_pbds::binomial_heap_tag，二项堆
__gnu_pbds::rc_binomial_heap_tag，冗余计数二项堆
__gnu_pbds::binary_heap_tag，二叉堆
__gnu_pbds::thin_heap_tag，类斐波那契堆

还有的文章介绍了 __gnu_pbds::priority_queue_tag，但似乎会编译错误。

这些堆的 push，pop 等基础操作和普通 STL 一样，不再说了。由于最常用、最快的是配对堆，下面介绍的操作都是配对堆中的。

__gnu_pbds::priority_queue<int>::point_iterator id;：创建一个迭代器，作用马上就说。
modify：两个参数，分别是迭代器和值，表示将这个迭代器代表的数改为这个值，再重新堆排序。它和 push 都会再返回一个迭代器。
erase：参数是一个迭代器，表示删除这个迭代器表示的值。
join：参数是另一个优先队列，表示将当前的优先队列合并到另一个优先队列，再将当前优先队列清空。

下面给出 OI-Wiki 上关于每种堆的性能测试的表格（图床比较慢，稍微等一会）：

此外关于优先队列（不是 queue 里的），还有一个叫做失效保证的操作，是用来维护迭代器的。这里不展开介绍。

`pb_ds trie`

这个字典树感觉不太好使，但可以骗分用。

它的头文件是 ext/pb_ds/trie_policy.hpp，但还要导入 ext/pb_ds/assoc_container.hpp。后面的 pb_ds 系列几乎都要导入这个头文件。

trie 定义起来比较固定。代码是：

trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> tr;

这段代码在实际应用时基本不会变，背过即可。

这个字典树的操作有这些：

insert，参数为一个字符串，表示向字典树插入这个字符串。会返回一个 pair，第一项表示插入的迭代器（失败返回 end），第二项表示插入是否成功。（bool 类型）
erase，参数同上，表示删除这个字符串。返回一个 bool，表示是否成功。
find，参数同上，表示寻找这个字符串。找不到返回原来字典树的 end。
join，参数为另一个字典树，表示将当前字典树合并到另一个字典树。再将当前字典树清空。
prefix_range，核心操作，参数为一个字符串，表示前缀为这个字符串的所有字符串的范围。它会返回一个 pair，其中第一项为范围的左端的迭代器，第二项为范围的右端的迭代器。具体使用方法见下。

//代码来源于 https://www.luogu.com.cn/article/zi85ltjk，有改写
typedef trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> Trie;//太长了，宏定义
Trie tr;
pair<Trie::iterator,Trie::iterator> range=tr.prefix_range(s);//求出范围
for(Trie::iterator it=range.first;it!=range.second;it++){//遍历迭代器
    cout<<*it<<endl;
}

`pb_ds list_update` 和 `forward_list`

这俩都是单向链表，而且特点差不多，就一起说了。

list_update 的头文件是 ext/pb_ds/assoc_container.hpp 和 ext/pb_ds/list_update_policy.hpp；而 forward list 的头文件在万能头里。

它们的创建方法是：

forward_list<T> lis;
list_update<T,null_type> lis;

其中 T 为数据类型。

forward_list 主要的操作比较多，先看它。

push_front，pop_front：在链表头部插入（删除）一个元素。
insert_after，erase_after：在给定的位置后面插入（删除）一个元素。
sort，对链表排序

再看 list_update：

begin，end：开头和结尾的迭代器。注意 end 指向结尾的下一个地址。
insert：在开头插入一个数。
erase：删除给出的数。

是的，list_update 甚至没有 insert_after 等，只能往头上插入数。

由于这俩都是链表，所以它们的插入、删除操作都是 O(1)，而随机访问大约是 O(n)。它们是单向，而 list 是双向，所以它们比 list 更省空间。除此之外，它们好像就没什么用了。

`pb_ds rope`

rope 虽然本质上不是 pb_ds，但我习惯将它和 pb_ds 一起讲。

rope 虽然使用块状链表实现的，但我们常用它来做各种可持久化数据结构的题目。

定义 rope 十分简单，先导入头文件 ext/rope，再 using namespace __gnu_cxx，然后直接 rope<T> r 即可，T 为数据类型，可以是结构体。特别地，如果 T 为 char 类型，则也可以定义为 crope r。它与 rope<char> r 没有什么区别。

rope 和 vector 类似，都是动态的，而且操作也很像。它的操作如下：

push_back，insert，erase：和 vector 一样，不再介绍。
substr：截取指定下标后的指定个数。（貌似传进一个左闭右开区间的左端点和右端点的迭代器也可以？）
append：和 push_back 类似，在后面插入元素。

crope 的一些操作比较特殊，如下：

insert：可以传入三个参数，分别是一个字符串（string 类型，记作 s）和两个数（记作 a,b），表示把 s 的前 b 位插入到当前 crope 第 a 位的后边。
erase：从给定下标开始删除给定数量个字符。
append：把给定字符串（string）从给定位置开始的给定数量个字符插入到当前 crope 末尾。

rope 被称为“持久化题目杀手”，是因为它上面这些操作的复杂度都小于等于 O(\sqrt n)。

`pb_ds` 平衡树

这个平衡树就是正宗 pb_ds 了。使用前需要导入 ext/pb_ds/assoc_container.hpp 和 ext/pb_ds/tree_policy.hpp。记得 using namespace __gnu_pbds;。

想要构造一个平衡树代码如下：

tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update> tr;

其中 T 依然是数据类型，rb_tree_tag 是树的类型（马上讲），tree_order_statistics_node_update 是树的更新方式。

pb_ds 自带三种树：

rb_tree_tag，红黑树，一般用这个
splay_tree_tag，Splay
ov_tree_tag，有序向量树

后面俩都容易超时，所以用第一种最好。

平衡树的操作都很简单，如下：

insert,erase：插入、删除。注意删除会把所有值等于给出值的元素都删掉。
order_of_key：求元素在平衡树里的排名。
find_by_order：返回第 k 小的值的迭代器。
join：把给出的另一棵平衡树并入自己，并将那棵平衡树清空。两棵树必须没有重复元素。
split：分裂，比给定值大的到另一棵平衡树，其它的留下。
lower_bound：返回第一个大于等于给定值的值的迭代器。
upper_bound：与上面类似，但返回的是严格大于给定值的值的迭代器。

上面这些操作的复杂度都小于等于 O(\log n)。

此外，这个平衡树还能自定义一些更强的操作，但一般用不到，而且本人太蒻了，所以请自行了解。

据我的测试，pb_ds 的平衡树比我手写的 Splay 和非旋 Treap 都快，所以放心用就行。

`pb_ds` 哈希表

它的头文件是 ext/pb_ds/assoc_container.hpp 和 ext/pb_ds/hash_policy.hpp，依旧要 using namespace __gnu_pbds;。

创建一个哈希表有两种方法：

cc_hash_table<int,bool> mp;
gp_hash_table<int,bool> mp;

第一个是“拉链”法，第二个是“探测”法。~~关于这两种哈希表谁快谁慢，很多 dalao 争了很长时间也没有定论，所以随便用一个就行。~~

哈希表操作更简单，和 map 完全一样：

[]，访问键所对应的值。
find，查找给定的键。如果没有返回 end。

不过没有 count 操作。

map 的复杂度为 O(n \log n)，而哈希表复杂度仅为 O(n)。所以它可以卡常用。

例题

这部分是本篇文章的例题。我将会使用上面介绍的数据结构完成。

`vstring`

太冷门了，就不给例题了。

`array`

就给一些数组练手题吧。

B2089 数组逆序重存放

简单题，模拟即可。

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n;
const int N=105;
array<int,N> a;//创建一个长度为 N 的数组
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    reverse(a.begin()+1,a.begin()+n+1);//反转
    for(int i=1;i<=n;i++){
        cout<<a[i]<<' ';
    }
    cout<<endl;
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 11:45:14
PROBLEM:B2089
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

`pb_ds` 优先队列

优先队列？那必须上合并果子和中位数了。

P1090 [NOIP 2004 提高组] 合并果子

简单题。考虑贪心，每次从果子堆中取出两个最小值合并即可。用优先队列维护最小值。

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define ll long long
#define endl '\n'
using namespace std;
int n;
const int N=10005;
array<int,N> a;//接着用 array
int ans=0;
__gnu_pbds::priority_queue<int,greater<int>,__gnu_pbds::pairing_heap_tag> q;//小根堆用 greater，并用配对堆
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        q.push(a[i]);//入队
    }
    while(q.size()>1){//不止一个，继续合并
        //取出两个最小值
        int x=q.top();q.pop();
        int y=q.top();q.pop();
        ans=ans+x+y;//增加总花费
        q.push(x+y);//合并，入队
    }
    cout<<ans<<endl;
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 15:24:11
PROBLEM:P1090
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

P1168 中位数

对顶堆板子题。

考虑创建一个大根堆和一个小根堆，并想象这两个堆的顶对着，呈一个平躺的沙漏型，左半边是大根堆。这样有一个性质：只要保证大根堆的根小于小根堆的根，那么大根堆所有元素肯定小于小根堆所有元素。（想一想，为什么。）

每读入一个数，先入右边小根堆。如果这个数特别小，跑到了小根堆的根，还比大根堆的根小，那它就和大根堆的根交换。

不但如此，我们还需要保证小根堆元素个数始终和大根堆差一个。如果差的不止一个，就把小根堆的根塞到大根堆里。这样中位数就是小根堆或大根堆的根了。

#include<bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
#define ll long long
#define endl '\n'
using namespace std;
int n,a[100005];
__gnu_pbds::priority_queue<int,greater<int>,__gnu_pbds::pairing_heap_tag> sma;//小根堆
__gnu_pbds::priority_queue<int,less<int>,__gnu_pbds::pairing_heap_tag> big;//大根堆
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];//输入
        sma.push(a[i]);//先入小根堆
        if(big.size()==sma.size()-2){//个数差 2
            big.push(sma.top());//把小根堆的根塞到大根堆
            sma.pop();
        }
        if(!big.empty()&&sma.top()<big.top()){//大根堆没空 且 小根堆的根比大根堆的根小
            int tmp1=sma.top();sma.pop();
            int tmp2=big.top();big.pop();
            big.push(tmp1);sma.push(tmp2);//交换
        }
        if(i%2==1) cout<<sma.top()<<endl;//输出中位数
    }
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 15:34:16
PROBLEM:P1168
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

在这道题里，pb_ds 的优先队列比普通优先队列快 \frac{304}{121} \approx 2.5 倍。

`pb_ds trie`

当然要做模板了。

P8306 【模板】字典树

模板题，直接套即可。

但我们求出范围后，得到的两个迭代器不能相减，只能通过 O(n) 的复杂度求出范围的大小。这样就会超时，只得 32 分。可以通过 distance 函数实现。

我目前想不到优化方法，如果你有优化方法欢迎提出。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
int T;
#define Trie trie<string,null_type,trie_string_access_traits<>,pat_trie_tag,trie_prefix_search_node_update> //宏定义

void solve(){
    int n,m;
    cin>>n>>m;
    Trie tr;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        tr.insert(s);//插入所有字符串
    }
    for(int i=1;i<=m;i++){
        string s;
        cin>>s;
        auto ans=tr.prefix_range(s);//求出范围

//      cout<<ans.second-ans.first+1<<endl;第一种方法，CE

//      int cnt=0;
//      for(Trie::iterator it=ans.first;it!=ans.second;it++){//遍历迭代器
//          cnt++;
//      }
//      cout<<cnt<<endl;//第二种方法

        cout<<distance(ans.first,ans.second)<<endl;//第三种方法
    }
}
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--){
        solve();//多测函数好
    }
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 16:01:03
PROBLEM:P8306
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

`pb_ds list_update` 和 `forward_list`

也做模板题。

因为 forward_list 功能多，所以都用它实现。

B3631 单向链表

forward_list 比较逆天的一点是无法得到一个元素的后继。为了解决这个问题，我开了一个长度为 10^6 的数组，记录每个数的迭代器。详见代码。

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'
using namespace std;
int n;
forward_list<int> lis;
#define IT forward_list<int>::iterator
IT its[1000005]={lis.end()};//迭代器数组，初始化为 end 
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    lis.push_front(1);//先把 1 塞进去 
    its[1]=lis.begin();//1 的迭代器是 begin 
    for(int i=1,op,x,y;i<=n;i++){
        cin>>op;
        if(op==1){
            cin>>x>>y;
            its[y]=lis.insert_after(its[x],y);//往迭代器后面塞 y 
        }
        if(op==2){
            cin>>x;
            IT it=its[x];it++;//要求下一个迭代器 
            if(lis.end()!=it) cout<<*(it)<<endl;//要特判，否则 RE 
            else cout<<0<<endl;
        }
        if(op==3){
            cin>>x;
            lis.erase_after(its[x]);//删掉 
        }
    }
    return 0;
}
/*
---INFORMATIONS---
TIME:2025/5/8 16:42:38
PROBLEM:B3631
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

但是它常数比较大，比手写的慢。但能用就行。

十分感谢 @Alex866 帮我调代码！

`pb_ds rope`

使用 rope 可以实现许多块状链表可以实现的数据结构，以及大部分可持久化数据结构。

P1383 高级打字机

这道题可以看做让我们实现“可持久化字符串”。因为是字符串，所以可以使用 crope。

我们可以开一个 crope 类型的数组，直接记录每个版本。这样，每个操作直接模拟即可。

#include<bits/stdc++.h>
#include<ext/rope> 
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_cxx;
int n;
crope a,s[100005];//当前文章 每次操作后的文章 
int cnt=0;
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        char op;
        cin>>op;
        if(op=='T'){
            char x;
            cin>>x;
            a.push_back(x);//追加字符 
            s[++cnt]=a;//新一次操作，放到数组里 
        }
        if(op=='U'){
            int x;
            cin>>x;
            crope tmp=s[cnt-x];//往回x次操作 
            s[++cnt]=tmp;//新一次操作 
            a=tmp;//更改当前文章 
        }
        if(op=='Q'){
            int x;
            cin>>x;
            cout<<a[x-1]<<endl;//直接输出 
        }
    }
    return 0;
}
/*
---INFORMATIONS---
TIME:2025/5/8 17:26:10
PROBLEM:P1383
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

P6166 [IOI 2012] scrivener

与上题几乎完全一样，直接从上面代码改即可。

#include<bits/stdc++.h>
#include<ext/rope> 
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_cxx;
int n;
crope a,s[100005];//当前文章 每次操作后的文章 
int cnt=0;
signed main(int argc,char *argv[]){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        char op;
        cin>>op;
        if(op=='T'){
            char x;
            cin>>x;
            a.push_back(x);//追加字符 
            s[++cnt]=a;//新一次操作，放到数组里 
        }
        if(op=='U'){
            int x;
            cin>>x;
            crope tmp=s[cnt-x];//往回x次操作 
            s[++cnt]=tmp;//新一次操作 
            a=tmp;//更改当前文章 
        }
        if(op=='P'){
            int x;
            cin>>x;
            cout<<a[x]<<endl;//直接输出 
        }
    }
    return 0;
}
/*
---INFORMATIONS---
TIME:2025/5/8 17:26:61
PROBLEM:P6166
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

P3391 【模板】文艺平衡树

这题不是可持久化，思路有点难想。我们先建两个 rope，一个从 1 到 n（记作 a），另一个从 n 到 1（记作 a'）。对于每次操作，我们可以把两个数组操作的区间单独剖出来，再倒着放回去，最后输出 a 即可。

例如，一共 5 个数，输入 2 4，流程如下图：

理解了这张图，就不难写出代码了——吗？

由于 rope 常数有点大，所以本题有些许卡常。但也没有太困难，改动下面两点即可：

i++，i-- 替换为 ++i，--i。
int 替换为 unsigned int。

下面放出卡常前和卡常后的代码进行对比参考。

//卡常前，#4 TLE
#include<bits/stdc++.h>
#include<ext/rope>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_cxx;
int n,m;
rope<int> a,a_;//一个正序一个倒序
void modify(int l,int r){
    if(l>r) return;//特判
    r++;
    rope<int> tmp,tmp_;
    tmp=a.substr(a.begin()+l,a.begin()+r);//剖出来
    tmp_=a_.substr(a_.begin()+n-r,a_.begin()+n-l);

    a=a.substr(a.begin(),a.begin()+l)+
      tmp_+
      a.substr(a.begin()+r,a.end());//和图中式子完全一样
    a_=a_.substr(a_.begin(),a_.begin()+n-r)+
       tmp+
       a_.substr(a_.begin()+n-l,a_.end());
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++) a.push_back(i);//正序
    for(int i=n;i>=1;i--) a_.push_back(i);//倒序
    for(int i=1,l,r;i<=m;i++){
        cin>>l>>r;
        modify(l-1,r-1);
    }
    for(int i=0;i<n;i++){//切记从 0 开始
        cout<<a[i]<<' ';
    }
    cout<<endl;
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 19:58:00
PROBLEM:P3391
CODE BY __CrossBow_EXE__ Luogu uid967841
不是啊，从八点推到十点
*/

//卡常后，AC，#4 948ms
#include<bits/stdc++.h>
#include<ext/rope>
#define ll long long
#define endl '\n'
#define uns unsigned
using namespace std;
using namespace __gnu_cxx;
uns int n,m;
rope<uns int> a,a_;//一个正序一个倒序
void modify(int l,int r){
    if(l>r) return;//特判
    rope<uns int> tmp,tmp_;
    tmp=a.substr(a.begin()+l,a.begin()+r);//剖出来
    tmp_=a_.substr(a_.begin()+n-r,a_.begin()+n-l);

    a=a.substr(a.begin(),a.begin()+l)+
      tmp_+
      a.substr(a.begin()+r,a.end());//和图中式子完全一样
    a_=a_.substr(a_.begin(),a_.begin()+n-r)+
       tmp+
       a_.substr(a_.begin()+n-l,a_.end());
}
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(uns int i=1;i<=n;++i) a.push_back(i);//正序
    for(uns int i=n;i>=1;--i) a_.push_back(i);//倒序
    for(uns int i=1,l,r;i<=m;++i){
        cin>>l>>r;
        modify(l-1,r);//左闭右开
    }
    for(uns int i=0;i<n;i++){//切记从 0 开始
        cout<<a[i]<<' ';
    }
    cout<<endl;
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 19:58:00
PROBLEM:P3391
CODE BY __CrossBow_EXE__ Luogu uid967841
不是啊，从八点推到十点
*/

P3402 可持久化并查集

这是一道比较普通的可持久化题目。

我们知道，并查集的核心就是父亲数组 f。因此我们用 rope 维护 f 数组即可。

代码可以参考题解。

P3835 【模板】可持久化平衡树

比较难的可持久化问题。可以参考题解。

`pb_ds` 平衡树

做一下模板题。

P3369 【模板】普通平衡树

似乎很简单，直接调用各种函数即可。但 pb_ds 里的平衡树有一个缺点，那就是它会去重。所以，我们可以把每个需要插入的数进行“加密”操作。

具体如何操作呢？很简单，如果我们想要插入 x，而它是第 cnt 个被插入的数，那么我们可以插入 2^{20}\times x+cnt。用代码表示，就是 (x<<20)+cnt。这样，就能保证平衡树中没有相同元素。想要得到 x 也很简单，直接将这个数除以 2^{20}，即右移 20 位即可。

但有时，毒瘤出题人会卡掉左移 20 位（这题没卡）。很简单，左移的位数微调一下即可。

此外，本题也可以用 rope 解决。请读者自行尝试。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> tr;
int n;
int cnt=0;
#define to(x,i) (((1ll*x)<<20)+i)//加密
#define bk(x) (x>>20)//解密 
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,op,x;i<=n;i++){
        cin>>op>>x;
        if(op==1) tr.insert(to(x,++cnt));
        if(op==2) tr.erase(tr.lower_bound(to(x,0)));//不必加上cnt
        if(op==3) cout<<tr.order_of_key(to(x,0))+1<<endl;
        if(op==4) cout<<bk(*tr.find_by_order(x-1))<<endl;//答案解密 
        if(op==5) cout<<bk(*(--tr.lower_bound(to(x,0))))<<endl;
        if(op==6) cout<<bk(*(tr.upper_bound(to(x,n))))<<endl;
    }
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 21:51:40
PROBLEM:P3369
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

`pb_ds` 哈希表

关于哈希表的题很多，也是只做模板。

P3370 【模板】字符串哈希

~~被迫不自觉，望原谅。~~

这题很简单，对于每个输入的字符串，先判断有没有在哈希表里出现过，如果出现过就跳过，否则标记为出现过。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
int n;
gp_hash_table<string,bool> mp;
int ans=0;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        if(mp.find(s)==mp.end()){//找到了
            ans++;
            mp[s]=1;
        }else continue;//没找到，跳过
    }
    cout<<ans<<endl;
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 21:55:51
PROBLEM:P3370
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

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

也比较简单，开两个哈希表，一个记录所有同学的名字，一个记录教练念过的名字，再判断即可。

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define ll long long
#define endl '\n'
using namespace std;
using namespace __gnu_pbds;
int n,m;
gp_hash_table<string,bool> mp,rd;
signed main(){
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        string s;
        cin>>s;
        mp[s]=1;//有这名同学
    }
    cin>>m;
    for(int i=1;i<=m;i++){
        string s;
        cin>>s;
        if(rd.find(s)==rd.end()){//没念过
            if(mp.find(s)!=mp.end()) cout<<"OK"<<endl;//有这名同学
            else cout<<"WRONG"<<endl;//没有这名同学
        }else{//念过了
            cout<<"REPEAT"<<endl;
        }
        rd[s]=1;//标记
    }
    return 0;
}
/*
---INFORMATIONS---
TIME:2025-05-08 22:00:00
PROBLEM:P2580
CODE BY __CrossBow_EXE__ Luogu uid967841
*/

到此为止，我就介绍完了这九个数据结构的使用方法。但这些只是整个 C++ 扩展库的冰山一角，还有更多有趣而冷门的数据结构等着大家去发现探索。

别急着走，结尾有彩蛋！

参考资料

比STL还STL？——平板电视
【转载】浅谈 pb_ds 库及其在OI其他算竞中的应用
实用 STL —— rope 学习笔记
C++ STL forward_list容器完全攻略
OI-Wiki 序列式容器

致谢

感谢上面提到的参考资料的作者。
感谢洛谷用户 @Great_Influence，博客园用户 @shen_ben 的代码为我带来了启发。
感谢你读完了这篇文章。关注、点赞、收藏后再走吧！

放在最后面的话

你有没有觉得，这么多头文件记起来很麻烦？其实两个头文件就能解决：bits/stdc++.h 和 bits/extc++.h。但后者在 Dev-C++ 中无法使用，换成小熊猫 C++ 才可以。

什么？你还不会配置小熊猫 C++？快去看我的往期文章吧！

还有一些无聊的统计：

本文共 20520 字符，一张图片，阅读完大约需要十分钟。

就到这里吧，感谢您的观看。

2025.5.8 By @__CrossBow_EXE__

幸甚至哉，歌以咏志。

5.13 更新内容

下面是作者在 2025.5.13 更新的内容。

作者看到大家就本文章展开了一系列讨论，这里补充一下。

`bits/extc++.h` 的使用

首先就是头文件 bits/extc++.h 的问题。我们除了使用小熊猫 C++，还可以在 MinGW 的官网上把 G++ 升级到最新版，即可使用这个头文件。

当然，有时候官网比较慢，这里直接给出 Github 上的下载直链。

下载解压完之后，我们需要配置环境变量。打开控制面板，搜索“编辑系统环境变量”，打开，在弹出的窗口中点击“环境变量”，双击打开“系统变量”中的 Path，新建一个变量。接着先别动，回到解压后的 MinGW64 文件夹，打开其中名为 bin 的子文件夹，并复制其地址。回到环境变量配置窗口，在新的变量中粘贴上刚才复制的地址。接着点击“确定”，一步一步退出即可。

接着，按下快捷键 Win+R，输入 cmd，在命令行中输入 gcc -v。如果输出了一大串东西，而且最后一行是 gcc 的版本（我给出的下载链接版本为 15.1.0），那就说明配置成功了。

主播主播，你的 MinGW64 确实很强，但还是太吃电脑操作了，有没有什么简单又强势的方法推荐一下？

有的兄弟，有的，这样简单的方法当然有了。注意到 bits/extc++.h 去除掉多于内容后，源代码不长：

#if __cplusplus < 201103L
#include <bits/stdtr1c++.h>
#else
#include <bits/stdc++.h>
#endif
#if __cplusplus >= 201103L
# include <ext/aligned_buffer.h>
#endif
#include <ext/alloc_traits.h>
#include <ext/atomicity.h>
#include <ext/cast.h>
#include <ext/iterator>
#include <ext/numeric_traits.h>
#include <ext/pointer.h>
#include <ext/typelist.h>
#include <ext/type_traits.h>
#if _GLIBCXX_HOSTED
#include <ext/algorithm>
#include <ext/bitmap_allocator.h>
#if __cplusplus >= 201103L
# include <ext/cmath>
#endif
#include <ext/concurrence.h>
#include <ext/debug_allocator.h>
#include <ext/extptr_allocator.h>
#include <ext/functional>
#include <ext/malloc_allocator.h>
#include <ext/memory>
#include <ext/mt_allocator.h>
#include <ext/new_allocator.h>
#include <ext/numeric>
#include <ext/pod_char_traits.h>
#include <ext/pool_allocator.h>
#if __cplusplus >= 201103L
# include <ext/random>
#endif
#include <ext/rb_tree>
#include <ext/rope>
#include <ext/slist>
#include <ext/stdio_filebuf.h>
#include <ext/stdio_sync_filebuf.h>
#include <ext/throw_allocator.h>
#include <ext/vstring.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/list_update_policy.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/trie_policy.hpp>
#ifdef _GLIBCXX_HAVE_ICONV
#include <ext/codecvt_specializations.h>
#include <ext/enc_filebuf.h>
#endif
#endif

所以，我们直接用上面的代码替代 bits/extc++.h 即可。

再说一句，本章内容不是重点，所以请不要讨论本章内容。

有关标题的说明

这一部分将会逐字解析题目，防止读者产生误解。

“【5.13 更新】”：表示本文经过了更新，更新日期为 5.13 日。
“超超超超超”：表示非常、十分
“冷门”：重点词句。作者所说的“冷门”不是指使用人数少，而是指使用频率不高，但十分有用。（所以请不要在评论区发类似“某某某不冷门啊”的内容了。）
“的 9 个”：点名前面的词语都是对后面的 9 个东西的修饰。
“C++ 自带数据结构”：也很重要，间接说明这些数据结构可以在 OI 考场上使用。

写在后面的话

这次我要感谢 @ttq012，他给这次补充的内容开了个头。

但上面说了这么多，还是不如小熊猫 C++ 简便……

什么？你还不会配置小熊猫 C++？快去看我的往期文章吧！

依旧有一些无聊的统计：

本文共 23399 字符，1 张图片，阅读大约需要 15 分钟。

就到这里吧，感谢您的观看。

2025.5.13 By @__CrossBow_EXE__

幸甚至哉，歌以咏志。

【5.13 更新】超超超超超冷门的 9 个 C++ 自带数据结构

前言

介绍

vstring

array

pb_ds 优先队列

pb_ds trie

pb_ds list_update 和 forward_list

pb_ds rope

pb_ds 平衡树

pb_ds 哈希表

例题

vstring

array

B2089 数组逆序重存放

pb_ds 优先队列

P1090 [NOIP 2004 提高组] 合并果子

P1168 中位数

pb_ds trie

P8306 【模板】字典树

pb_ds list_update 和 forward_list

B3631 单向链表

pb_ds rope

P1383 高级打字机

P6166 [IOI 2012] scrivener

P3391 【模板】文艺平衡树

P3402 可持久化并查集

P3835 【模板】可持久化平衡树

pb_ds 平衡树

P3369 【模板】普通平衡树

pb_ds 哈希表

P3370 【模板】字符串哈希

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

参考资料

致谢

放在最后面的话

5.13 更新内容

bits/extc++.h 的使用

有关标题的说明

写在后面的话

`vstring`

`array`

`pb_ds` 优先队列

`pb_ds trie`

`pb_ds list_update` 和 `forward_list`

`pb_ds rope`

`pb_ds` 平衡树

`pb_ds` 哈希表

`vstring`

`array`

`pb_ds` 优先队列

`pb_ds trie`

`pb_ds list_update` 和 `forward_list`

`pb_ds rope`

`pb_ds` 平衡树

`pb_ds` 哈希表

`bits/extc++.h` 的使用