Loi_Vampire's Blog

自己选择的路,就算跪着也要走完

12/21
21:57
平衡树 数据结构

BZOJ 1251 序列终结者 splay

Description

网上有许多题,就是给定一个序列,要你支持几种操作:A、B、C、D。一看另一道题,又是一个序列 要支持几种操作:D、C、B、A。尤其是我们这里的某人,出模拟试题,居然还出了一道这样的,真是没技术含量……这样 我也出一道题,我出这一道的目的是为了让大家以后做这种题目有一个“库”可以依靠,没有什么其他的意思。这道题目 就叫序列终结者吧。 【问题描述】 给定一个长度为N的序列,每个序列的元素是一个整数(废话)。要支持以下三种操作: 1. 将[L,R]这个区间内的所有数加上V。 2. 将[L,R]这个区间翻转,比如1 2 3 4变成4 3 2 1。 3. 求[L,R]这个区间中的最大值。 最开始所有元素都是0。

Input

第一行两个整数N,M。M为操作个数。 以下M行,每行最多四个整数,依次为K,L,R,V。K表示是第几种操作,如果不是第1种操作则K后面只有两个数。

Output

对于每个第3种操作,给出正确的回答。

Sample Input

4 4
1 1 3 2
1 2 4 -1
2 1 3
3 2 4

Sample Output

2
【数据范围】 N<=50000,M<=100000。

HINT

 

Source

 

一道splay的题。

首先,为了保证数字在平衡树中保持在序列中的相对位置,在插入的时候,采用类似分治的方法。

对区间进行操作时,将l-1的位置转到根,r+1的位置转到跟的右儿子,则要操作的区间在l-1和r+1之间,打标记即可。

 

12/20
14:27
平衡树 数据结构 树套树 线段树

BZOJ 3196 二逼平衡树 树套树

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作: 1.查询k在区间内的排名 2.查询区间内排名为k的值 3.修改某一位值上的数值 4.查询k在区间内的前驱(前驱定义为小于x,且最大的数) 5.查询k在区间内的后继(后继定义为大于x,且最小的数)

Input

第一行两个数 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的后继

Output

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

Sample Input

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

Sample Output

2
4
3
4
9

HINT

1.n和m的数据范围:n,m<=50000 2.序列中每个数的数据范围:[0,1e8]

3.虽然原题没有,但事实上5操作的k可能为负数

Source

 

一道树套树的题,还是比较裸的…然而调了半天,终归还是我太弱啊 TAT

 

12/19
15:04
平衡树 数据结构

BZOJ 3223 文艺平衡树 splay

Description

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:翻转一个区间,例如原有序序列是5 4 3 2 1,翻转区间是[2,4]的话,结果是5 2 3 4 1

Input

第一行为n,m n表示初始序列有n个数,这个序列依次是(1,2……n-1,n) m表示翻转操作次数 接下来m行每行两个数[l,r] 数据保证 1<=l<=r<=n

Output

输出一行n个数字,表示原始序列经过m次变换后的结果

Sample Input

5 3
1 3
1 3
1 4

Sample Output

4 3 2 1 5

HINT

N,M<=100000

Source

平衡树

区间翻转,交换左右儿子即可。

 

12/19
08:38
平衡树 数据结构 模板

BZOJ 3224 普通平衡树 splay

Description

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

  1. 插入x数
  2. 删除x数(若有多个相同的数,因只删除一个)
  3. 查询x数的排名(若有多个相同的数,因输出最小的排名)
  4. 查询排名为x的数
  5. 求x的前驱(前驱定义为小于x,且最大的数)
  6. 求x的后继(后继定义为大于x,且最小的数)

Input

第一行为n,表示操作的个数,下面n行每行有两个数opt和x,opt表示操作的序号(1<=opt<=6)

Output

对于操作3,4,5,6每行输出一个数,表示对应答案

Sample Input

10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598

Sample Output

106465
84185
492737

HINT

1.n的数据范围:n<=100000 2.每个数的数据范围:[-1e7,1e7] 数据如下 http://pan.baidu.com/s/1jHMJwO2

Source

平衡树