P3369 【模板】普通平衡树(Treap/SBT)

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