P3380 【模板】二逼平衡树(树套树)

    • 512通过
    • 2.4K提交
  • 题目提供者 HansBug 站长团
  • 评测方式 云端评测
  • 标签 树套树 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms / 256MB

题解

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

    推荐的相关题目 显示

    题目描述

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

    1. 查询k在区间内的排名

    2. 查询区间内排名为k的值

    3. 修改某一位值上的数值

    4. 查询k在区间内的前驱(前驱定义为严格小于x,且最大的数,若不存在输出-2147483647)

    5. 查询k在区间内的后继(后继定义为严格大于x,且最小的数,若不存在输出2147483647)

    注意上面两条要求和tyvj或者bzoj不一样,请注意

    输入输出格式

    输入格式:

    第一行两个数 n,m 表示长度为n的有序序列和m个操作

    第二行有n个数,表示有序序列

    下面有m行,opt表示操作标号

    若opt=1 则为操作1,之后有三个数l,r,k 表示查询k在区间[l,r]的排名

    若opt=2 则为操作2,之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数

    若opt=3 则为操作3,之后有两个数pos,k 表示将pos位置的数修改为k

    若opt=4 则为操作4,之后有三个数l,r,k 表示查询区间[l,r]内k的前驱

    若opt=5 则为操作5,之后有三个数l,r,k 表示查询区间[l,r]内k的后继

    输出格式:

    对于操作1,2,4,5各输出一行,表示查询结果

    输入输出样例

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

    说明

    时空限制:2s,128M

    $ n,m \leq 5\cdot {10}^4 $ 保证有序序列所有值在任何时刻满足 $ [0, {10} ^8] $

    题目来源:bzoj3196 / Tyvj1730 二逼平衡树,在此鸣谢

    此数据为洛谷原创。(特别提醒:此数据不保证操作5、6一定存在,故请务必考虑不存在的情况

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