题解 P3369 【【模板】普通平衡树(Treap/SBT)】

Rye_Catcher

2018-02-22 11:04:06

Solution

### STL真是个好东西。 最近在看pb_ds库及vector和set的用法,就想用这三种操作来实现一下普通平衡树,结果pb_ds中的rbtree不支持重复值,而本蒟蒻也看不懂不懂各大佬用pb_ds的实现,况且应该有人已经贴上了题解。我就发一发vector和set(其实是multiset)的题解吧。~~(只不过蒟蒻的我我根本不会打splay)~~ 代码都很短,操作其实也很基础。 ------------ #### vector版: - 你要知道: - lower_bound(first,last,x)在first和last中的前闭后开区间进行查找,其中如果寻找的x存在,那么lower_bound返回一个迭代器指向其中**第一个**x元素。 时间复杂度:O(logN) - upper_bound(first,last,x)在first和last中的前闭后开区间进行查找,返回一个迭代器指向最后一个x元素的下一个位置(就是说返回在保持顺序的情况下,可插入x的**最后一个位置**或者说就是返回x的后继) 时间复杂度:O(logN) - vector.insert(pos,x)在pos处插入一个x vector.erase(pos,x)在删除pos处的x 时间复杂度:这个不太清楚,貌似是O(N) 然后你就能看懂下面的代码了 ```cpp #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <vector> #include <cctype> using namespace std; vector <int>a; int read() { int x=0;char ch;short int neg=0;ch=getchar(); while(!isdigit(ch)){ neg|=(ch=='-');ch=getchar(); } while(isdigit(ch)){ x=x*10+ch-48;ch=getchar(); } return neg?-x:x; } int main() { int n,op; cin>>n; while(n--) { cin>>op; register int x=read(); switch(op){ case(1):a.insert(upper_bound(a.begin(),a.end(),x),x);break; case(2):a.erase(lower_bound(a.begin(),a.end(),x));break; case(3): cout<<lower_bound(a.begin(),a.end(),x)-a.begin()+1<<endl;break; case(4): cout<<a[x-1]<<endl;break; case(5): cout<<*--lower_bound(a.begin(),a.end(),x)<<endl;break; case(6): cout<<*upper_bound(a.begin(),a.end(),x)<<endl;break; } } return 0; } ``` 可以看出,我们是有序地加入元素,vector本身也是有序的 开O2跑得~~比香港记者还~~快,不开O2好像最慢的300多ms ------------ #### set版: C++ STL中的set好像是用红黑树实现的,但是它并不支持重复元素,所以我们只能用multiset,然而用multiset(其实set也是)搞排名之类的就好复杂了......看网上说好像是STL中的红黑树并没有维护什么size域,我也不太懂。 - 你要知道: - insert和erase和上面基本一样的 - distance(pos1,pos2)返回一个int值为pos1与pos2之间的距离,pos1,pos2为指向同一容器的迭代器。 时间复杂度:O(N) - advance(pos,k)一个void的函数,让pos这个迭代器前进k步 时间复杂度:O(N) - set.equal_range(x),它返回的一队迭代器,因此是pair类型,定义时需注意。 具体用法详见这: http://blog.csdn.net/zhongguoren666/article/details/8463249 时间复杂度:O(logN) 由于上面操作的时间复杂度以及常数较大,用set开O2依旧会T掉几个点,我这个代码在O2优化时还会玄学WA了一个,我也不清楚为什么,不知道有没有dalao搞一个更优的set做法 ```cpp #include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <set> #include <cctype> using namespace std; multiset <int>a; int read() { int x=0;char ch;short int neg=0;ch=getchar(); while(!isdigit(ch)){ neg|=(ch=='-');ch=getchar(); } while(isdigit(ch)){ x=x*10+ch-48;ch=getchar(); } return neg?-x:x; } int main() { int n,op; cin>>n; while(n--) { cin>>op; register int x=read(); if(op==1)a.insert(upper_bound(a.begin(),a.end(),x),x); else if(op==2)a.erase(lower_bound(a.begin(),a.end(),x)); else if(op==3)cout<<distance(a.begin(),a.upper_bound(x))<<endl; else if(op==4) {multiset<int>::iterator it =a.begin(); //int k=distance(a.begin(),a+x); advance(it,x-1); cout<<' '<<*it<<endl;} else if(op==5) cout<<*--lower_bound(a.begin(),a.end(),x)<<endl; else { pair<multiset<int>::const_iterator,multiset<int>::const_iterator> it; it=a.equal_range(x);cout<<*it.second<<endl;}//cout<<*upper_bound(a.begin(),a.end(),x)<<endl; } return 0; } ``` 当然,STL不会支持更多变式操作况且现在裸题也越来越少,但它用来优化某些东西或是对拍还是非常有用的。 本蒟蒻也要开始学splay了