题解 P3369 【【模板】普通平衡树（Treap/SBT）】

## 声明：最好是有一定平衡树基础的同学再来看这个题解，你首先得会手写:D **这里向大家介绍一个神奇的宝贝：pb\_ds库的tree。** tree的功能相当强大，而这一题就可以用到里面封装的平衡树。 我尝试了Splay和红黑树(红黑树用的别人的代码)，发现果然RBT快了不少，Splay耗时接近RBT的三倍了。 使用pb\_ds，背代码的能力必不可少，比如用tree就需要两个很长的头文件，具体参考代码。 但是需要注意的是，由于这个模板的erase只需要删除一个数，因此我们需要对插入的数进行简单的处理~~虽然这个“简单的”处理和奇特的处理lowerbound耗费了我一两个小时才写完，我觉得我智商也是没救了~~ 关于pb\_ds的详细内容见代码吧。当然，建议还是去**网上找博客**详细深挖。 最后，我爱pb\_ds，我爱STL。 ```cpp #include<cstdio> #include<iostream> #include<ext/pb_ds/tree_policy.hpp> #include<ext/pb_ds/assoc_container.hpp>//头文件 #define f(i,a,b) for(i=a;i<=b;++i) using namespace __gnu_pbds;//由于定义tree时逐个添上这个东西太难缠了，于是干脆就这样了 typedef long long ll; tree<ll,null_type,std::less<ll>,splay_tree_tag,tree_order_statistics_node_update>st;//splay,只要把splay改为rb就是红黑树XD,另外注意std::less int main() { int i,j,m; ll ans,x,y; scanf("%d",&m); f(i,1,m) { scanf("%lld%lld",&x,&y); if(x==1)st.insert((y<<20)+i);//简单的处理 else if(x==2)st.erase(st.lower_bound(y<<20)); else if(x==3)printf("%d\n",st.order_of_key(y<<20)+1); else { if(x==4)ans=*st.find_by_order(y-1); if(x==5)ans=*--st.lower_bound(y<<20); if(x==6)ans=*st.lower_bound((y+1)<<20); printf("%lld\n",ans>>20);//一并处理ans } }//f(i,0,st.size()-1)printf("%lld ",(*st.find_by_order(i))>>20);//check return 0; } ```