P5076 【深基16.例7】普通二叉树（简化版）讲解

· · 题解

二叉搜索树？我为什么要用？
这道题是可以直接模拟的呀。
下面我们就来分析它的每一个操作：

  1. 定义数 x 的排名为集合中小于 x 的数的个数 +1。 查询 x 的排名。
    由于集合中没有重复元素， 故可以直接使用 STL 中的 lower_bound()， 复杂度为 O(\log_2n)。
  2. 查询排名为 x(1\le x) 的数。
    直接调用，O(1) 解决。
  3. 求 x 的前驱（前驱定义为小于 x，且最大的数）。 若不存在则输出 -2147483647。
    再次 lower_bound() 二分查找， 复杂度为 O(\log_2n)。
  4. 求 x 的后继（后继定义为大于 x，且最小的数）。 若不存在则输出 2147483647。
    upper_bound() 查找， 同上。
  5. 插入一个数 x。
    先 lower_bound() 找出应插入的位置，再插入（用动态数组是因为不想手写 insert() 函数）， 复杂度为 O(n)。
    总体复杂度为 O(n^2)。
    代码： 
    #include<bits/stdc++.h>
#define int long long
#define reg register
#define inl inline
#define INF 2147483647
using namespace std;
vector<int>g;
int q,op,x;
inl int read(){
reg int f=1,x=0;
reg char ch=getchar();
while(ch<'0'||ch>'9'){
    if(ch=='-') f=-1;
    ch=getchar();
}
while(ch>='0'&&ch<='9'){
    x=(x<<1)+(x<<3)+(ch^48);
    ch=getchar();
}                
return f*x;      
}                 
inl void write(int x){
if(x<0){         
    x=-x;        
    putchar('-');
}
if(x>=10) write(x/10);
putchar(x%10^48);
}
inl void solve(){
reg int xx;
op=read();
x=read();
switch(op){
    case 1:
        xx=lower_bound(g.begin(),g.end(),x)-g.begin();
        write(xx);
        putchar('\n');
        break;
    case 2:
        write(g[x]);
        putchar('\n');
        break;
    case 3:
        xx=lower_bound(g.begin(),g.end(),x)-g.begin();
        if(xx-1==g.end()-g.begin()||!(xx-1)) write(-INF);
        else write(g[xx-1]);
        putchar('\n');
        break;
    case 4:
        xx=upper_bound(g.begin(),g.end(),x)-g.begin();
        if(xx==g.end()-g.begin()) write(INF);
        else write(g[xx]);
        putchar('\n');
        break;
    case 5:
        g.insert(lower_bound(g.begin(),g.end(),x),x);
        break;
}
return;
}
signed main(){
g.push_back(0);
q=read();
while(q--) solve();
return 0;
}