题目描述

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

查询k在区间内的排名

查询区间内排名为k的值

修改某一位值上的数值

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

查询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各输出一行,表示查询结果


口胡了两天的板子,这里是线段树套FHQTreap
FHQTreap常数略大..
对于每个线段树节点开一个独立的平衡树
然后建树的时候枚举每个点,插入该点所在区间的节点就行了
删除同理

1.求K的rank 将K在线段树所在区间的平衡树里面的rank值加一块就好了
2.求rank K的数是多少,二分答案然后调用1.判断一下
3.修改,先执行删除操作,删除原来的数字,然后在原一维数组修改,然后执行插入操作
4.&5.求区间包含的每个线段树节点的该数的前驱和后继然后取max,min就行了
线段树每个节点存平衡树根节点

 

 



说点什么

avatar
  Subscribe  
提醒