P3369 【模板】普通平衡树

    • 17.2K通过
    • 46.7K提交
  • 题目提供者 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类违反进行处理。