Loi_Vampire's Blog

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

02/20
10:42
可持久化数据结构 数据结构

BZOJ 4546 codechef XRQRS 可持久化trie

Description

给定一个初始时为空的整数序列(元素由1开始标号)以及一些询问: 类型1:在数组后面就加入数字x。 类型2:在区间L…R中找到y,最大化(x xor y)。 类型3:删除数组最后K个元素。 类型4:在区间L…R中,统计小于等于x的元素个数。 类型5:在区间L…R中,找到第k小的数。

Input

输入数据第一行为一个整数q,表示询问个数,接下来q行,每行一条询问 对应题目描述。 类型1的询问格式为“1 x”。 类型2的询问格式为“2 L R x”。 类型3的询问格式为“3 k”。 类型4的询问格式为“4 L R x”。 类型5的询问格式为“5 L R k”。

Output

对于每个2、4、5询问输出一行对应答案

Sample Input

10

1 8

5 1 1 1

1 2

2 2 2 7

2 2 2 7

1 1

4 2 2 2

2 1 2 3

4 1 3 5

1 6

Sample Output

8

2

2

1

8

2

HINT

令N表示每次询问前数组中元素的个数

1<=L<=R<=N

1<=x<=500,000

对于第三类询问 1<=k<=N

对于第五类询问 k<=R-L+1

1<=N<=500,000

Source

 

Solution

可持久化trie,写法和主席树差不多,注意数组大小。