二叉树 #二叉搜索树¶

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

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

题目描述¶

您需要写一种数据结构，来维护一些数（都是 \(10^9\) 以内的数字）的集合，最开始时集合是空的。其中需要提供以下操作，操作次数 \(q\) 不超过 \(10^4\)：

查询 \(x\) 数的排名（排名定义为比当前数小的数的个数 \(+1\)。若有多个相同的数，应输出最小的排名）。
查询排名为 \(x\) 的数。
求 \(x\) 的前驱（前驱定义为小于 \(x\)，且最大的数）。若未找到则输出 \(-2147483647\)。
求 \(x\) 的后继（后继定义为大于 \(x\)，且最小的数）。若未找到则输出 \(2147483647\)。
插入一个数 \(x\)。

输入格式¶

第一行是一个整数 \(q\)，表示操作次数。

接下来 \(q\) 行，每行两个整数 \(op,x\)，分别表示操作序号以及操作的参数 \(x\)。

输出格式¶

输出有若干行。对于操作 \(1,2,3,4\)，输出一个整数，表示该操作的结果。

样例 #1¶

样例输入 #1¶

样例输出 #1¶

方法一：二叉树¶

TODO:

方法二：multiset¶

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

multiset<int> q;
int n, order;

int main()
{
    q.insert(-2147483647);
    q.insert(2147483647);

    cin >> n;
    while (n--)
    {
        int op, x;
        cin >> op >> x;
        if (op == 1)
        {
            auto it = q.lower_bound(x);

            order = 0;

            for (auto i = q.begin(); i != it; i++, order++)
                ;
            cout << order << endl;
        }
        else if (op == 2)
        {
            order = -1;
            for (int i : q)
                if (++order == x)
                    cout << i << endl;
        }
        else if (op == 3)
        {
            auto it = q.lower_bound(x);

            cout << *--it << endl;
        }
        else if (op == 4)
        {
            cout << *q.upper_bound(x) << endl;
        }
        else
        {
            q.insert(x);
        }
    }

    return 0;
}