P3369 【模板】普通平衡树

    • 11.2K通过
    • 30K提交
  • 题目提供者 HansBug 站长团
  • 评测方式 云端评测
  • 标签 平衡树 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作:

    1. 插入 $x$ 数
    2. 删除 $x$ 数(若有多个相同的数,因只删除一个)
    3. 查询 $x$ 数的排名(排名定义为比当前数小的数的个数 $+1$ 。若有多个相同的数,因输出最小的排名)
    4. 查询排名为 $x$ 的数
    5. 求 $x$ 的前驱(前驱定义为小于 $x$ ,且最大的数)
    6. 求 $x$ 的后继(后继定义为大于 $x$ ,且最小的数)

    输入输出格式

    输入格式:

    第一行为 $n$ ,表示操作的个数,下面 $n$ 行每行有两个数 $opt$ 和 $x$ , $opt$ 表示操作的序号( $ 1 \leq opt \leq 6 $ )

    输出格式:

    对于操作 $3,4,5,6$ 每行输出一个数,表示对应答案

    输入输出样例

    输入样例#1: 复制
    10
    1 106465
    4 1
    1 317721
    1 460929
    1 644985
    1 84185
    1 89851
    6 81968
    1 492737
    5 493598
    输出样例#1: 复制
    106465
    84185
    492737

    说明

    时空限制:1000ms,128M

    1.n的数据范围: $ n \leq 100000 $

    2.每个数的数据范围: $[-{10}^7, {10}^7]$

    来源:Tyvj1728 原名:普通平衡树

    在此鸣谢

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。