P3369 【模板】普通平衡树题解

langmouren · 2025-02-07 11:19:34 · 题解

PBDS

前言

什么？数据加强版？我不信！

本题解初步介绍了 pbds 库，并对 pbds 库在本题进行了应用。

什么是 pbds 库

它是一个扩展库，我们可以使用以下头文件来方便的引用它（有的人喜欢叫它平板电视库（雾））。

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

DevC++ 人机时刻

由于神秘原因，windows 下的 DevC++ 无法直接使用 #include<bits/extc++.h>，我们可以点击下面的报错：

他会转到这个界面：

我们可以在其中选择需要的引用，粘贴到自己的文件中代替 #include<bits/extc++.h>，这样就不会报错了.

它能干什么

它封装了 hash、tree、trie、priority_queue 四种数据结构，在这里我们使用到了 tree。

为什么要使用

它避免了长篇大论地编写平衡树代码，而是直接让我们使用封装好的版本。
它可以在 NOI 系列比赛中使用。

如何声明

tree<数据类型,无映射,排列方式,树的类型,更新方式> 变量名称;

数据类型：int、long long 等，一般使用 long long
无映射：使用 null_type
排列方式：less 从小到大 greater 从大到小，本题使用 less<long long>
树的类型：rd_tree、ov_tree、splay_tree，看名字就知道是什么树，建议使用 rd_tree 即红黑树，因为它快。
更新方式：除非你需要自写 update，否则使用 tree_order_statistics_node_update。

如何使用

tre.insert(x); //插入x;
tre.erase(x); //删除x;
tre.order_of_key(x); //返回x的排名;
tre.find_by_order(k); //返回第k小的值的迭代器;
tre.lower_bound(x); //返回第一个大于等于x的元素的迭代器;
tre.upper_bound(x); //返回第一个大于x的元素的迭代器;

tre.join(b); //树的合并;
tre.split(a,b); //树的分裂;

使用时注意事项

红黑树会自动去重，所以以其作为树的类型时，我们要对数据进行哈希，一般使用 long long 作为数据类型，将其左移，再加上循环中的 i。
数据很（毒）大（瘤）的时候可能会卡掉哈希，可以通过数据结构记录读入时间作为不重复变量，重载运算符；或是修改左移位数（它总不能移多少都卡吧？！）。

代码实现

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

tree<long long,null_type,less<long long>,rb_tree_tag,tree_order_statistics_node_update> tre;

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        long long op,k;
        scanf("%lld%lld",&op,&k);
        if(op==1) tre.insert((k<<20)+i);
        else if(op==2) tre.erase(tre.lower_bound(k<<20));
        else if(op==3) printf("%lld\n",tre.order_of_key(k<<20)+1);
        else if(op==4) printf("%lld\n",(*tre.find_by_order(k-1))>>20);
        else if(op==5) printf("%lld\n",(*--tre.lower_bound(k<<20))>>20);
        else printf("%lld\n",(*tre.upper_bound((k<<20)+n))>>20);
    }
    return 0;
}

超绝代码量。

其他

提交记录

更多 pbds 库用法可见洛谷日报。

P3369 【模板】普通平衡树 题解