平板电视(pb_ds)

pb_ds

前置代码：

CPP

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

需要小熊猫c++.

堆(priority_queue)

用法和STL中的优先队列差不多
定义方式：__gnu_pbds::priority_queue<int,greater<int>> pq[1000010];

成员函数

push(): 向堆中压入一个元素，返回该元素位置的迭代器。
pop(): 将堆顶元素弹出。
top(): 返回堆顶元素。
size() 返回元素个数。
empty() 返回是否非空。
modify(point_iterator, const key): 把迭代器位置的 key 修改为传入的 key，并对底层储存结构进行排序。
erase(point_iterator): 把迭代器位置的键值从堆中擦除。
join(__gnu_pbds::priority_queue &other): 把 other 合并到 *this 并把 other 清空。

性能

例题

【模板】可并堆2

题目描述

给定正整数

n

和

m

以及一个长为

n

的整数序列

a_{1,\dots,n}

。

你需要维护序列

a_{1,\dots,n}

以及

n

个集合

S_{1,\dots,n}

，初始时

S_i=\{i\}

。

接下来要进行以下四种操作共

m

次，每次操作形如：

0 x y：表示将元素 $y$ 从集合 $S_x$ 中删去。保证此时元素 $y$ 在集合 $S_x$ 中。
1 x：表示询问 $\min_{i\in S_x} a_i$ ，保证此时集合 $S_x$ 非空。
2 x y：将集合 $S_y$ 中并入 $S_x$ 并清空集合 $S_y$ 。保证此时集合 $S_x,S_y$ 均非空，且此次操作后不会再出现涉及集合 $S_y$ 的操作。
3 x y z：表示将 $a_y$ 赋值为 $z$ 。保证此时元素 $y$ 在集合 $S_x$ 中，且 $z<a_y$ 。

不难发现这是一道堆的模板题，所以现在请你完成它。

代码：

CPP

1234567891011121314151617#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_pbds;
__gnu_pbds::priority_queue<int,greater<int>> pq[1000010];
__gnu_pbds::priority_queue<int,greater<int>>::point_iterator p[1000010];
int main(){
	ios::sync_with_stdio(0);cin.tie();int n,m;cin>>n>>m;
	for(int i=1,x;i<=n;++i) cin>>x,p[i]=pq[i].push(x);
	while(m--){
		int x,y,z,op;cin>>op;
		if(op==0) cin>>x>>y,pq[x].erase(p[y]);
		if(op==1) cin>>x,cout<<pq[x].top()<<"\n";
		if(op==2) cin>>x>>y,pq[x].join(pq[y]);
		if(op==3) cin>>x>>y>>z,pq[x].modify(p[y],z);
	}
}

哈希表

可以较好的解决unordered_map常数过大的问题

cc_hash_table:拉链法解决哈希冲突问题
gp_hash_table:探测法解决哈希冲突问题

和unordered_map的操作类似，find查找键值，没有count函数，[]访问键对应的值

时间复杂度

O(n)

,比map少一个

log

平衡树

定义方式

CPP

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

功能

insert(x)：向树中插入一个元素 x，返回 std::pair<point_iterator, bool>，其中第一个元素代表插入位置的迭代器，第二个元素代表是否插入成功。
erase(x)：从树中删除一个元素/迭代器 x。如果 x 是迭代器，则返回指向 x 下一个的迭代器（如果 x 是 end() 则返回 end()）；如果 x 是 Key，则返回是否删除成功（如果不存在则删除失败）。
order_of_key(x)：返回严格小于 x 的元素个数（以 Cmp_Fn 作为比较逻辑），即从 0 0 开始的排名。
find_by_order(x)：返回 Cmp_Fn 比较的排名所对应元素的迭代器。
lower_bound(x)：返回第一个不小于 x 的元素所对应的迭代器（以 Cmp_Fn 作为比较逻辑）。
upper_bound(x)：返回第一个严格大于 x 的元素所对应的迭代器（以 Cmp_Fn 作为比较逻辑）。
join(x)：将 x 树并入当前树，x 树被清空（必须确保两树的比较函数和元素类型相同）。
split(x,b)：以 Cmp_Fn 比较，小于等于 x 的属于当前树，其余的属于 b 树。
empty()：返回是否为空。
size()：返回大小。

例题

【模板】平衡树

CPP

1234567891011121314151617181920212223242526#include<bits/stdc++.h>
#include<bits/stdc++.h>
#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(){
	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)));
		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;
}

提示

因为pb_ds版平衡树会自动去重，所以要把每个数先左移20位，输出时再右移20位，这样可以避免重复的数被去掉。

例：一个数

x

是第

cnt

个要被插入平衡树的数，那么我们就可以把(x<<20)+cnt插入平衡树中。

文章操作