洛谷题单指南-二叉树-P5076 【深基16.例7】普通二叉树（简化版）

原题链接：https://www.luogu.com.cn/problem/P5076

题意解读：此题本质上是要实现一个二叉搜索树的功能。

解题思路：

从数据规模10^4来看，只要复杂度在n^2范围内基本上是可以通过的，下面给出两种做法：

1、有序数组法

对应5个操作的实现逻辑如下：

操作一：查x的排名。直接通过二分查找>=x的第一个数的位置pos，pos即x的排名，复杂度O(logN)；

操作二：查排名x的数。直接返回x下标的元素，复杂度O(1)；

操作三：x的前驱。通过二分查找>=x的最小的数的位置pos，x的前驱即pos-1位置的数，不存在要输出 −2147483647，复杂度O(logN)；

操作四：x的后继。通过二分查找<=x的最大的数的位置pos，x的后继即pos+1位置的数，不存在要输出2147483647，复杂度O(logN)；

操作五：插入x。通过二分查找>=x的最小的数的位置pos，如果pos不存在，则将x添加到最后，否则从pos开始把所有数往后移一位，将x放入pos，复杂度<=O(logN + N)。

总体复杂度<O(N^2)

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 10005;

int a[N], idx;

int bs1(int x)
{
    int l = 1, r = idx, ans = -1;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(a[mid] >= x) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    if(ans == -1) ans = idx + 1; //如果不存在，要找的位置就是当前最后一个数的下一个位置
    return ans;
}

int bs2(int x)
{
    int l = 1, r = idx, ans = -1;
    while(l <= r)
    {
        int mid = (l + r) >> 1;
        if(a[mid] <= x) ans = mid, l = mid + 1;
        else r = mid - 1;
    }
    if(ans == -1) ans = 0; //如果不存在，要找的位置就是当前第一个数前一个位置
    return ans;
}

int main()
{
    int q, op, x;
    cin >> q;
    while(q--)
    {
        cin >> op >> x;
        if(op == 1)
        {
            int r = bs1(x); //查找第一个>=x的位置，即x的排名
            cout << r << endl;
        } 
        else if(op == 2) cout << a[x] << endl; //返回排名x的数
        else if(op == 3) 
        {
            int pos = bs1(x); //查找>=x的最小的数的位置pos
            if(pos - 1 > 0) cout << a[pos - 1] << endl; //x的前驱即pos-1位置的数
            else cout << -2147483647 << endl; //不存在要输出 −2147483647
        }
        else if(op == 4) 
        {
           int pos = bs2(x); //查找<=x的最大的数的位置pos
           if(pos + 1 <= idx) cout << a[pos + 1] << endl; //x的后继即pos+1位置的数
           else cout << 2147483647 << endl; //不存在要输出2147483647
        }
        else
        {
            int pos = bs1(x); //查找>=x的最小的数的位置pos
            
            if(pos == idx + 1) a[++idx] = x; //如果没有找到，说明所有数都比x小，添加到最后
            else 
            {
                for(int i = idx; i >= pos; i--) 
                    a[i + 1] = a[i]; //从pos开始把所有数往后移一位
                a[pos] = x; //将x放入pos
                idx++; //最后一个元素的位置更新
            }
        }
    }

    return 0;
}

2、set法（底层是红黑树-一种平衡的二叉搜索树）

set有两个实现了二分查找功能的函数要介绍一下：

s.lower_bound(x); //返回容器中第一个大于等于x的数的迭代器 

s.upper_bound(x);//返回容器中第一个大于x的数的迭代器

对应5个操作的实现逻辑如下：

操作一：查x的排名。通过lower_bound(x)查找第一个>=x的数的迭代器it，从迭代器s.begin()遍历到it，累计cnt即为x的排名，复杂度<=O(logN + N)；

操作二：查排名x的数。从迭代器s.begin()遍历x次，取第x个元素的值，复杂度<=O(N)；

操作三：x的前驱。通过lower_bound(x)查找第一个>=x的数的迭代器it，x的前驱即it--位置的数，不存在要输出 −2147483647，复杂度O(logN)；

操作四：x的后继。通过upper_bound(x)查找第一个>x的数的迭代器it，x的后继*it，不存在要输出2147483647，复杂度O(logN)；

操作五：插入x。通过insert(x)插入数据，复杂度O(logN)。

总体复杂度<O(N^2)

100分代码：

#include <bits/stdc++.h>
using namespace std;

set<int> tree;

int main()
{
    int q, op, x;
    cin >> q;
    while(q--)
    {
        cin >> op >> x;
        if(op == 1)
        {
            int cnt = 1;
            set<int>::iterator end = tree.lower_bound(x);  //查找第一个>=x的数的迭代器
            for(set<int>::iterator it = tree.begin(); it != end; it++) cnt++; //从迭代器s.begin()遍历到it，累计cnt即为x的排名
            cout << cnt << endl;
        } 
        else if(op == 2) 
        {
            int cnt = 1;
            set<int>::iterator it = tree.begin();
            while(it != tree.end() && cnt != x) it++, cnt++; //从迭代器s.begin()遍历x次，取第x个元素的值
            cout << *it << endl;
        }
        else if(op == 3) 
        {
            set<int>::iterator it = tree.lower_bound(x);  //查找第一个>=x的数的迭代器it
            if(it != tree.begin()) cout << *(--it) << endl; //x的前驱即--it位置的数
            else cout << -2147483647 << endl; //不存在要输出 −2147483647
        }
        else if(op == 4) 
        {
            set<int>::iterator it = tree.upper_bound(x); //查找第一个>x的数的迭代器it
            if(it != tree.end()) cout << *it << endl; //x的后继*it
            else cout << 2147483647 << endl; //不存在要输出2147483647
        }
        else tree.insert(x); //插入数据
    }

    return 0;
}