P3835 【模板】可持久化平衡树

    • 308通过
    • 1.1K提交
  • 题目提供者 HansBug 站长团
  • 评测方式 云端评测
  • 标签 Treap 可持久化 平衡树 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms-2000ms / 512MB

题解

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

    推荐的相关题目 显示

    题目背景

    本题为题目 普通平衡树 的可持久化加强版。

    数据已经经过强化

    题目描述

    您需要写一种数据结构(可参考题目标题),来维护一些数,其中需要提供以下操作(对于各个以往的历史版本):

    1. 插入x数

    2. 删除x数(若有多个相同的数,因只删除一个,如果没有请忽略该操作)

    3. 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数,因输出最小的排名)

    4. 查询排名为x的数

    5. 求x的前驱(前驱定义为小于x,且最大的数,如不存在输出-2147483647)

    6. 求x的后继(后继定义为大于x,且最小的数,如不存在输出2147483647)

    和原本平衡树不同的一点是,每一次的任何操作都是基于某一个历史版本,同时生成一个新的版本。(操作3, 4, 5, 6即保持原版本无变化)

    每个版本的编号即为操作的序号(版本0即为初始状态,空树)

    输入输出格式

    输入格式:

    第一行包含一个正整数N,表示操作的总数。

    接下来每行包含三个正整数,第 $i$ 行记为 $v_i, opt_i, x_i$ 。

    $v_i$ 表示基于的过去版本号( $ 0 \leq v_i < i$ ),$opt_i$ 表示操作的序号( $ 1 \leq opt \leq 6 $ ), $x_i$ 表示参与操作的数值

    输出格式:

    每行包含一个正整数,依次为各个3,4,5,6操作所对应的答案

    输入输出样例

    输入样例#1: 复制
    10
    0 1 9
    1 1 3
    1 1 10
    2 4 2
    3 3 9
    3 1 2
    6 4 1
    6 2 9
    8 6 3
    4 5 8
    输出样例#1: 复制
    9
    1
    2
    10
    3

    说明

    数据范围:

    对于28%的数据满足: $ 1 \leq n \leq 10 $

    对于44%的数据满足: $ 1 \leq n \leq 2\cdot {10}^2 $

    对于60%的数据满足: $ 1 \leq n \leq 3\cdot {10}^3 $

    对于84%的数据满足: $ 1 \leq n \leq {10}^5 $

    对于92%的数据满足: $ 1 \leq n \leq 2\cdot {10}^5 $

    对于100%的数据满足: $ 1 \leq n \leq 5\cdot {10}^5 $ , $-{10}^9 \leq x_i \leq {10}^9$

    经实测,正常常数的可持久化平衡树均可通过,请各位放心

    样例说明:

    共10次操作,11个版本,各版本的状况依次是:

    1. $[]$

    2. $[9]$

    3. $[3, 9]$

    4. $[9, 10]$

    5. $[3, 9]$

    6. $[9, 10]$

    7. $[2, 9, 10]$

    8. $[2, 9, 10]$

    9. $[2, 10]$

    10. $[2, 10]$

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