- #include <ext/pb_ds/assoc_container.hpp>
- #include <ext/pb_ds/tree_policy.hpp>
- // 或者直接用
- #include <bits/extc++.h>
- using namespace __gnu_pbds;
- tree<double, null_type, greater<double>, rb_tree_tag, tree_order_statistics_node_update> T;
- // 这个东西有一点点长
- // 第一个参数是数据类型
- // 第二个要填 null_type, 低版本编译器填 null_mapped_type
- // 第三个填比较函数 std::greater<> or std::Less<> or cmp
- // 第四个填树的类型, 有 rb_tree_tag 红黑树和 splay_tree_tag
- // 第五个是为了支持查询第 k 大和排名的一个参数 //tree_order_statistics_node_update
https://www.luogu.org/recordnew/show/20375729 平衡树模板题.
- #include <bits/stdc++.h>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- tree<double, null_type, Less<double>, rb_tree_tag, tree_order_statistics_node_update> T;
- int main()
- {
- //freopen("3369.in", "r", stdin);
- //freopen("3369.out", "w", stdout);
- int q, opt, x;
- scanf("%d", &q);
- for (int i = 1; i <= q; ++ i)
- {
- scanf("%d%d", &opt, &x);
- if(opt == 1)
- T.insert(x + i * 1e-6);
- // 插入一个数
- if(opt == 2)
- T.erase(T.lower_bound(x));
- // 删除一个数
- if(opt == 3)
- printf("%d\n", (int)T.order_of_key(x) + 1);
- // 查询一个数的排名
- if(opt == 4)
- printf("%d\n", (int)*T.find_by_order(x - 1));
- // 查询第 k 小的数 返回的是一个迭代器 这里 k 是从 0 开始算的, 意思是最小的数是第 0 小的
- if(opt == 5)
- printf("%d\n", (int)round(*(-- T.lower_bound(x))));
- // 查询一个数的前驱
- if(opt == 6){
- printf("%d\n", (int)round(*T.lower_bound(x + 1)));
- }
- // 查询一个数的后继
- }
- return 0;
- }
- #include<bits/stdc++.h>
- #include<ext/pb_ds/assoc_container.hpp>
- #define pr pair<int,int>
- #define inf 1000000000
- using namespace std;
- using namespace __gnu_pbds;
- typedef tree<pr,null_type,Less<pr>,rb_tree_tag,tree_order_statistics_node_update> rbtree;
- typedef rbtree::iterator ITER;
- char c[10];
- rbtree q;
- ITER r;
- int tot=0;
- int main(){
- int n,x;
- scanf("%d",&n);
- while(n--){
- scanf("%s%d",c,&x);
- switch(c[0]){
- case 'I':q.insert(pr(x,tot++));break;
- case 'D':r=q.lower_bound(pr(x,0)),q.erase(r);break;
- case 'M':
- if(c[1]=='I')r=q.begin(),printf("%d\n",(*r).first);
- else r=q.end(),r--,printf("%d\n",(*r).first);
- break;
- case 'P':
- r=q.lower_bound(pr(x,0));
- if(r==q.begin())puts("0");
- else r--,printf("%d\n",*r);
- break;
- case 'S':
- r=q.upper_bound(pr(x,inf));
- if(r==q.end())puts("0");
- else printf("%d\n",*r);
- break;
- case 'K':printf("%d\n",(*q.find_by_order(x-1)).first);break;
- case 'R':printf("%d\n",q.order_of_key(pr(x,0))+1);break;
- }
- }
- return 0;
- }
首先就是大名鼎鼎的 PDF 介绍:
C++ 的 pb_ds 库在 OI 中的应用
看完了之后, 再看一下具体实现吧, 他没有怎么说具体使用
以下拿 普通平衡树 做了板子, 写了一份代码
我用的是 rbtree 和 hashtable
关于这两个东西的说明在代码里有注释的
代码:(168ms, 和手写 splay 几乎相当)
- #include<cstdio>
- #include<cstdlib>
- #include<cstring>
- #include<cmath>
- #include<iostream>
- #include<algorithm>
- #include<ext/pb_ds/assoc_container.hpp> //tree 和 hash_table 的共用头文件
- #include<ext/pb_ds/tree_policy.hpp> //tree 头文件
- #include<ext/pb_ds/hash_policy.hpp> //hash_table 头文件
- #define ll long long
- #define max(a,b) a>b?a:b
- #define min(a,b) a<b?a:b
- using namespace std;
- using namespace __gnu_pbds;// 最好加上这一句, 不然你会写得很累
- inline void read(ll &x){
- x=0;int f=1;char ch=' ';
- while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
- x*=f;
- }
- typedef tree<ll,null_type,Less<ll>,rb_tree_tag,tree_order_statistics_node_update> rbtree;
- // 这一行是 rbtree
- // 第一个是 key 类型
- // 第二个就填 null_type
- // 第三个是比较函数, Less 表示从小到大, greater 表示从大到小
- // 第四个是树的类型, 建议使用 rbtree , 跑得最快, splay 是 splay_tree_tag
- // 第五个是支持 order_of_key 和 find_by_order 的必须
- typedef gp_hash_table<ll,int> hashtable;
- // 这一行是 hash_table
- // 第一个是 key 类型
- // 第二个是 value 类型
- // hash_table 有两个, 分别是 cc_hash_table 和 gp_hash_table
- // 实测 gp_hash_table 更快
- rbtree t;
- hashtable h;
- # include <bits/stdc++.h>
- # include <ext/pb_ds/tree_policy.hpp>
- # include <ext/pb_ds/hash_policy.hpp>
- # include <ext/pb_ds/assoc_container.hpp>
- using namespace std ;
- using namespace __gnu_pbds ;
- inline int read ( ) {
- register int x, c ;
- bool opt ( 1 ) ;
- while ( isspace ( c = getchar ( ) ) && ( c != 45 ) ) ;
- if ( c == 45 ) opt = 0, c = getchar ( ) ;
- for ( x = -48 + c ; isdigit ( c = getchar ( ) ) ; ( x *= 10 ) += c - 48 ) ;
- return opt ? x : -x ;
- }
- gp_hash_table <int, int> H ;
- tree <pair < int, int>, null_type, Less <pair < int, int>>, rb_tree_tag, tree_order_statistics_node_update> T ;
- //tree <pair < int, int>, null_type, Less <pair < int, int>>, rb_tree_tag, tree_order_statistics_node_update> T ;
- int main ( ) {
- int n ( read ( ) ) ;
- while ( n -- ) {
- static int opt, x ;
- opt = read ( ), x = read ( ) ;
- switch ( opt ) {
- case 1 : {
- T.insert ( make_pair ( x, ++H[x] ) ) ;
- printf("%d\n", H[x]);
- break ;
- }
- case 2 : {
- T.erase ( make_pair ( x, H[x] --) ) ;
- break ;
- }
- case 3 : {
- printf ( "%d\n", ( int ) T.order_of_key ( make_pair ( x, 0 ) ) + 1 ) ;
- break ;
- }
- case 4 : {
- printf ( "%d\n", T.find_by_order ( x - 1 ) -> first ) ;
- break ;
- }
- case 5 : {
- printf ( "%d\n", T.find_by_order ( T.order_of_key ( make_pair ( x, 0 ) ) - 1 ) -> first ) ;
- break ;
- }
- case 6 : {
- printf ( "%d\n", T.upper_bound ( make_pair ( x, INT_MAX ) ) -> first ) ;
- break ;
- }
- }
- }
- }
- https://ac.nowcoder.com/acm/contest/908/D
- #include <bits/stdc++.h>
- #include <ext/pb_ds/tree_policy.hpp>
- #include <ext/pb_ds/assoc_container.hpp>
- using namespace std;
- using namespace __gnu_pbds;
- typedef pair<int, int> pii;
- const int N = 100005;
- tree<pii, null_type, Less<pii>, rb_tree_tag,
- tree_order_statistics_node_update> t;
- int a[3][N];
- gp_hash_table<int,int> mp;
- int main()
- {
- int n, m;
- while(~scanf("%d", &n)) {
- t.clear();
- mp.clear();
- for(int i = 1; i <= n; i++) {
- scanf("%d", &a[1][i]);
- mp[ a[1][i] ]++;
- t.insert( pii(a[1][i], mp[ a[1][i] ]) );
- }
- for(int i = 1; i <= n; i++) {
- scanf("%d", &a[2][i]);
- mp[ a[2][i] ]++;
- t.insert( pii(a[2][i], mp[ a[2][i] ]) );
- }
- scanf("%d", &m);
- while(m--) {
- int q, pos, val, k;
- scanf("%d%d%d%d", &q, &pos, &val, &k);
- t.erase( t.lower_bound( pii(a[q][pos], 0) ) );
- a[q][pos] = val;
- mp[val]++;
- t.insert(pii(val, mp[val]));
- printf("%d\n", (*t.find_by_order(k - 1)).first);
- }
- }
- return 0;
- }
平衡树
来源: http://www.bubuko.com/infodetail-3115814.html