XCPC Notes

Appearance

发布时间：2024-06-06
cpp
#include<bits/extc++.h>//有些OJ会编译错误

引入 ​

cpp
#include<bits/extc++.h>
cpp
#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> //字典树使用
using namespace __gnu_pbds;

哈希表 ​

cpp
//相当于unordered_map
__gnu_pbds::cc_hash_table<T1, T2> h;//拉链法，速度慢但不会被卡
__gnu_pbds::gp_hash_table<T1, T2> h;//探测法
//拉链法不会被卡哈希冲突，但探测法会

平衡树 ​

cpp
//方法
__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,有则为std::map，没有(即null_type)则为std::set
//Cmp_Fn,分别为less<>和greater<>对应递减与递增
/*******tag******/
rb_tree_tag:红黑树，一般用法
splay_tree_tag:splay树
ov_tree_tag:排序的vector
/****************/
//Node_Update,更新节点策略，使用tree_order_statistics_node_update后开启order_of_key,find_by_order方法
//Allocator,一般缺省不用

操作方法 ​

insert(x)插入，返回一个pair，[迭代器,bool]
erase(x)删除，返回bool
order_of_key(x)返回排名(从0开始)
find_by_order(x)返回排名对应的值
lower_bound(x)/upper_bound(x)二分查找
join(x)将树x加入
split(x,b)分为两棵树，当前树小于等于x,b大于x
empty()/size()

普通平衡树板子 ​

cpp
#include<bits/extc++.h>
using namespace __gnu_pbds;
#define TR tree<PII,null_type,less<PII>,rb_tree_tag,tree_order_statistics_node_update>
void solve(){
    TR tr;
    int q;
    cin>>q;
    int cnt=0;
    tr.insert({-INF,0});
    tr.insert({INF,0});
    while(q--){
        int op,x,ans;
        cin>>op>>x;
        if(op==1)tr.insert({x,++cnt});//pbds平衡树无法记录个数，因此使用pair，第二维代表编号
        else if(op==2)tr.erase(*tr.lower_bound({x,0}));
        else if(op==3)cout<<tr.order_of_key(*tr.lower_bound({x,0}))<<"\n";
        else if(op==4)cout<<tr.find_by_order(x)->first<<"\n";
        else if(op==5)cout<<(--tr.lower_bound({x,0}))->first<<"\n";
        else cout<<(tr.upper_bound({x,INF})->first)<<"\n";
    }
}

堆 ​

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

__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 内存分配器，同上

时间复杂度对比 ​

img

rope(实际为可持久化平衡树，实现块状链表) ​

cpp
#include<ext/rope>
using namespace __gnu_cxx;
rope<T> a;
a.push_back(x)
a.insert(pos,x)//在pos处插入x
a.erase(pos,x)//在pos处删除x个元素
a.at(x),a[x]//随机访问
a.length()或a.size()//大小
a.insert(pos,T *s,int n)//将数组区间[0,n-1]插入到pos
a.append(T *s,int pos,int n)//[pos,pos+n-1]插入到队尾
a.substr(int pos,int len)//提取[pos,pos+len-1]
a.substr(begin,end)//迭代器区间
a.copy(int pos,int len,T *s)//将[pos,pos+len-1]复制到数组s
a.replace(int pos,int n,T *s)//将[pos,pos+n-1]替换成数组s的值
//copy和replace为相反操作可以实现区间翻转
//保险起见，所有操作均认为根号n的复杂度
//空间复杂度未知，慎用

Wenwei Lin · 2022 — 2025