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

本文最后更新于 2025年3月2日 下午

引用P5076 【深基16.例7】普通二叉树（简化版） 题目描述 您需要写一种数据结构，来维护一些数（都是绝对值 $10^9$ 以内的数）的集合，最...

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

题目描述

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

  1. 定义数 $x$ 的排名为集合中小于 $x$ 的数的个数 $+1$。查询数 $x$ 的排名。注意 $x$ 不一定在集合里。
  2. 查询排名为 $x(x\ge 1)$ 的数。保证集合里至少有 $x$ 个数。
  3. 求 $x$ 的前驱（前驱定义为小于 $x$，且最大的数）。若不存在则输出 $-2147483647$。
  4. 求 $x$ 的后继（后继定义为大于 $x$，且最小的数）。若不存在则输出 $2147483647$。
  5. 插入一个数 $x$，本题的数据保证插入前 $x$ 不在集合中。

保证执行 $1,3,4$ 操作时，集合中有至少一个元素。

输入格式

第一行是一个整数 $q$，表示操作次数。

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

输出格式

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

输入输出样例 #1

输入 #1

7
5 1
5 3
5 5
1 3
2 2
3 3
4 3

输出 #1

2
3
1
5

题解

方法1

使用BST

一个实现如下

代码CPP · 134 行
#include<bits/stdc++.h>
using namespace std;

using i64=long long;
using u64=unsigned long long;
using u32=unsigned;
using u128=unsigned __int128;

const int inf=2147483647;

//需要实现：按照排名找权值，按照权值找排名，找前驱，找后继，插入
struct node{
    int v;
    int lchild=0,rchild=0;
    int siz; //(两子树+自己本身)的大小（结点数之和）
}bst[100010]; //以1为根结点

int cnt=0; //表示总结点数目

void insert(int v,int idx){ //v表示权值，idx表示当前的结点编号
    bst[idx].siz++;
    if(v>bst[idx].v){ //说明v应该插入到右子树
        if(bst[idx].rchild!=0){
            insert(v,bst[idx].rchild);
        }
        else{ //不存在右孩子
            cnt++;
            bst[cnt].v=v;
            bst[cnt].siz=1;
            bst[idx].rchild=cnt;
        }
    }
    else{
        if(bst[idx].lchild!=0){
            insert(v,bst[idx].lchild);
        }
        else{
            cnt++;
            bst[cnt].v=v;
            bst[cnt].siz=1;
            bst[idx].lchild=cnt;
        }
    }
}

int findPre(int v){
    int idx=1; //从根结点开始搜索
    int ans=-inf;
    while(idx){
        if(bst[idx].v<v){
            ans=bst[idx].v;
            idx=bst[idx].rchild;
        }
        else{
            idx=bst[idx].lchild;
        }
    }
    return ans;
}

int findPost(int v){
    int idx=1;
    int ans=inf;
    while(idx){
        if(bst[idx].v>v){
            ans=bst[idx].v;
            idx=bst[idx].lchild;
        }
        else{
            idx=bst[idx].rchild;
        }
    }
    return ans;
}

int fromRankfindV(int rk,int idx){ //idx是当前遍历到的根结点
    int leftSize=bst[bst[idx].lchild].siz;
    if(rk<=leftSize){
        return fromRankfindV(rk,bst[idx].lchild);
    }
    else if(rk==leftSize+1){
        return bst[idx].v;
    }
    else{
        return fromRankfindV(rk-leftSize-1,bst[idx].rchild);
    }
    
}

//标准做法
int fromVfindRank(int v,int idx){ //最后返回值还需要再+1
    if(idx==0) return 0;
    if(v<=bst[idx].v){
        return fromVfindRank(v,bst[idx].lchild);
    }
    else{
        return bst[bst[idx].lchild].siz+1+fromVfindRank(v,bst[idx].rchild);
    }
}

int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    int q;
    cin>>q;

    while(q--){
        int op;
        int x;
        cin>>op>>x;
        if(op==1){
            cout<<fromVfindRank(x,1)+1<<"\n";
        }
        else if(op==2){
            cout<<fromRankfindV(x,1)<<"\n";
        }
        else if(op==3){
            cout<<findPre(x)<<"\n";
        }
        else if(op==4){
            cout<<findPost(x)<<"\n";
        }
        else if(op==5){
            if(cnt==0){
                cnt=1;
                bst[1].v=x;
                bst[1].siz=1;
            }
            else insert(x,1);
        }
    }

    return 0;
}

但是找前驱和找后继的函数可以省略，因为可以先查询x的排名rank，然后查询排名为rank-1和rank+1的数，就分别是前驱和后继了。

如果rank+1>cnt或者rank-1<1，那么就可以分别输入inf和-inf

方法2

使用STL容器multiset

引用multiset的常见用法详解 multiset的定义 multiset 是一个集合容器，它可以存储多个相同的元素。换句话说，如果你有一堆重复的...

multiset的常见用法详解

multiset的定义

multiset 是一个集合容器，它可以存储多个相同的元素。换句话说，如果你有一堆重复的数，比如 3、5、5、5、7，你可以用multiset来妥善管理它们。与set不同的是，set不会允许重复的元素，而multiset非常欢迎重复元素的加入。

可以使用统一初始化的元素来创建

int main() {
    multiset<int> numbers = {3, 5, 5, 7, 3, 9};

    // 基于范围的for循环遍历multiset
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

注意，multiset会自动按升序排列元素。

如果是自定义类型，需要重载小于号

multiset内元素的访问

使用迭代器

multiset常用函数实例解析

insert()

略了

erase()

erase方法用来删除元素。但是要注意！如果你直接传入一个值，所有与这个值相同的元素都会被删除。如果你只想删除一个特定的元素，最好先找到它的迭代器，然后用这个迭代器来删除。

int main() {
    multiset<int> numbers = {3, 5, 5, 7};

    // 删除所有的5
    numbers.erase(5);

    // 打印当前的multiset
    for (int num : numbers) {
        cout << num << " ";
    }

    return 0;
}

如果只想删除第一个5

auto it = numbers.find(5);  // 找到第一个5
if (it != numbers.end()) {
    numbers.erase(it);  // 只删除找到的第一个5
}

size()

略了

clear()

略了

empty()

略

lower_bound()

略 和algorithm中的不一样

upper_bound()

略 和algorithm中的不一样

分析题目

1. 查询 x 数的排名

排名，说白了就是排序之后的x的下标。

我们只要用lower_bound方法，找到第一个x的位置。

然后从begin开始往后遍历容器，只要达到这个位置，就输出当前下标即可。

2.查询排名为 x 的数

遍历容器，只要当前排名到达x，就输出当前值。

（因为multiset容器无法进行随机访问）

3.求 x 的前驱（前驱定义为小于 x，且最大的数）

前驱，也就是x的前一个。

我们只要用lower_bound方法找到第一个x的位置，然后输出上一个就OK了。

4.求 x 的后继（后继定义为大于 x，且最小的数）。

后继，也就是第一个大于x的数。

我们可以用upper_bound方法，直接找到这个值。

5.插入一个数 x

直接用insert方法插入即可。

代码CPP · 75 行
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
multiset<int>q;
int n,t,x,order;
int main()
{
    q.insert(-0x7fffffff);
    q.insert(0x7fffffff);
    //提前放入这两个数，避免错误
    scanf("%d",&n);
    while(n--)
    {
        scanf("%d%d",&t,&x);
        if(t==1)
        {
            auto it=q.lower_bound(x);
            //可以写作multiset<int>::iterator，因为lower_bound方法返回的是迭代器
            // it 取得 x 的位置
            
            order=0;
            //order为排名
            
            for(auto i=q.begin();i!=it;i++,order++);
            //这里就处理出了x的排名——order
            
            printf("%d\n",order);
            //输出order即为答案
        }
        else if(t==2)
        {
            order=-1;
            //初值为-1是因为前面有一个-0x7fffffff，所以order要多跑一步

            for(int i:q)
                if(++order==x)
                //缩写，order先自增一，再判断是否与x相等
                //如果是(order++==x)，那就是先判断再自增，这里要尤其注意
                    printf("%d\n",i);
                //i就是容器里的值，输出i
        }
        else if(t==3)
        {
            auto it=q.lower_bound(x);
            //取得第一个大于等于x的值
            //也就是第一个x的位置
            //由于我们要取得前驱，所以it要自减一
            printf("%d\n",*--it);
            //这句是先自减，再输出，是缩写
            //等价于：
            /*
                it--;
                printf("%d\n",*it);
            */
            //因为是迭代器（指针），所以输出前面加 *
        }
        else if(t==4)
        {
            printf("%d\n",*q.upper_bound(x));
            //要取得后继，就是第一个大于x的值
            //用upper_bound方法取得第一个大于x的迭代器
            //输出即可
            //因为是迭代器（指针），所以输出前面加 *
        }
        else
        {
            q.insert(x);
            //直接添加即可
        }
    }
    return 0;
}