平板电视(pb_ds)

dw_dz · 2025-10-09 22:35:20 · 算法·理论

pb_ds

前置代码：

#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。

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

代码：

#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.

平衡树

定义方式

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()：返回大小。 ::cute-table{tuack}

  例题

  【模板】平衡树

  #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插入平衡树中。