题解：P3369 【模板】普通平衡树

ivyjiao · 2024-11-02 19:21:44 · 题解

这题有多少种解法啊？

这里介绍一种时间复杂度正确的且不是 pbds 的做法，类似 pbds，在 __gnu_cxx 库里。

一眼望去，这题的六个操作都可以用 vector 实现，那就直接用 vector 做行不行？

需要熟练运用 \text{insert},\text{erase} 等操作，思路十分简单，在这里不提了。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,op,x;
vector <int> vec; 
int main(){
    scanf("%d",&n);
    while(n--){
        scanf("%d %d",&op,&x);
        if(op==1) vec.insert(lower_bound(vec.begin(),vec.end(),x),x);
        else if(op==2) vec.erase(lower_bound(vec.begin(),vec.end(),x));
        else if(op==3) printf("%d\n",lower_bound(vec.begin(),vec.end(),x)-vec.begin()+1);
        else if(op==4) printf("%d\n",vec[x-1]);
        else if(op==5) printf("%d\n",vec[lower_bound(vec.begin(),vec.end(),x)-vec.begin()-1]);
        else printf("%d\n",vec[upper_bound(vec.begin(),vec.end(),x)-vec.begin()]);
    }
}

但是 vector 的 \text{insert} 和 \text{erase} 是 O(n) 的，只不过做了很多优化。

所以 vector 是能被卡掉的，虽然我没在网上找到像是卡掉 SPFA 一样的卡掉 vector 教程，但是肯定是能卡掉的。

但是 rope 的 \text{insert} 和 \text{erase} 都是严格 O(\log n) 的！本题 1\leq n\leq 10^5，O(\log n) 完全可过，时间复杂度 O(n\log n)，由于其常数巨巨巨大，在 n\leq 10^5 的情况下（不是本题，另外一道题）都能被卡到 900ms，经测试其常数约为 vector 的四倍，所以实际速度和 O(n\sqrt n) 没什么太大区别，也不能通过 n\leq 1.1\times 10^6 的加强版。

之所以说这个是因为很多人以为它跟块状链表放在一起就误认为它的 O(\sqrt n) 的数据结构，实际上原文也说了：

由于 rope 并不是真正的用块状链表来实现，所以它的时间复杂度并不等同于块状链表，而是相当于可持久化平衡树的复杂度 O(\log n)。

感觉这个东西比 rb_tree_tag 都要冷门？

代码：

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
using namespace __gnu_cxx;
int n,op,x;
rope<int>a; 
int main(){
    cin>>n;
    while(n--){
        cin>>op>>x;
        if(op==1) a.insert(lower_bound(a.begin(),a.end(),x)-a.begin(),x);
        if(op==2) a.erase(lower_bound(a.begin(),a.end(),x)-a.begin(),1);
        if(op==3) cout<<lower_bound(a.begin(),a.end(),x)-a.begin()+1<<endl;
        if(op==4) cout<<a[x-1]<<endl;
        if(op==5) cout<<a[lower_bound(a.begin(),a.end(),x)-a.begin()-1]<<endl;
        if(op==6) cout<<a[upper_bound(a.begin(),a.end(),x)-a.begin()]<<endl;
    }
}