Loi_Vampire's Blog

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

02/21
10:17
可持久化数据结构 数据结构

BZOJ 3166 [Heoi2013]Alo 可持久化trie

Description

Welcome to ALO ( Arithmetic and Logistic Online)。这是一个VR MMORPG , 如名字所见,到处充满了数学的谜题。 现在你拥有n颗宝石,每颗宝石有一个能量密度,记为ai,这些宝石的能量 密度两两不同。现在你可以选取连续的一些宝石(必须多于一个)进行融合,设为 ai, ai+1, …, a j,则融合而成的宝石的能量密度为这些宝石中能量密度的次大值 与其他任意一颗宝石的能量密度按位异或的值,即,设该段宝石能量密度次大值 为k,则生成的宝石的能量密度为max{k xor ap | ap ≠ k , i ≤ p ≤ j}。 现在你需要知道你怎么选取需要融合的宝石,才能使生成的宝石能量密度最大。

Input

第一行,一个整数 n,表示宝石个数。 第二行, n个整数,分别表示a1至an,表示每颗宝石的能量密度,保证对于i ≠ j有 ai ≠ aj。

Output

输出一行一个整数,表示最大能生成的宝石能量密度。

Sample Input

5

9 2 1 4 7

Sample Output

14

HINT

【样例解释】

选择区间[1,5],最大值为 7 xor 9。

对于 100%的数据有 1 ≤ n ≤ 50000, 0 ≤ ai ≤ 10^9

Source

加强型数据By Hta

Solution

窝真是太弱了……看了 黄学长的题解 才会做……

大体思路就是:

按照权值从大到小,把每个数的位置插入到set中去。

对于当前的数字x,在set中查询它的前驱的前驱,以及后继的后继,x的可行区间就为[前驱的前驱+1,x]和[x,后继的后继-1]。(为什么?这样的话,x在这两个区间内都是次大值)

然后就可以合并为一个区间啦,在可持久化trie中查询即可。

 

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,写法和主席树差不多,注意数组大小。

 

02/19
15:16
可持久化数据结构 数据结构

BZOJ 3261 最大异或和 可持久化trie

Description

给定一个非负整数序列 {a},初始长度为 N。
有 M个操作,有以下两种操作类型:

1 、A x:添加操作,表示在序列末尾添加一个数 x,序列的长度 N+1。 2 、Q l r x:询问操作,你需要找到一个位置 p,满足 l<=p<=r,使得:

a[p] xor a[p+1] xor ... xor a[N] xor x 最大,输出最大是多少。

Input

第一行包含两个整数 N ,M,含义如问题描述所示。
第二行包含 N个非负整数,表示初始的序列 A 。

接下来 M行,每行描述一个操作,格式如题面所述。

Output

假设询问操作有 T个,则输出应该有 T行,每行一个整数表示询问的答案。

Sample Input

5 5

2 6 4 3 6

A 1

Q 3 5 4

A 4

Q 5 7 0

Q 3 6 6

对于测试点 1-2,N,M<=5 。

对于测试点 3-7,N,M<=80000 。

对于测试点 8-10,N,M<=300000。

其中测试点 1, 3, 5, 7, 9保证没有修改操作。

对于 100%的数据,0<=a[i]<=10^7。

Sample Output

4

5

6

HINT

对于 100% 的数据, 0<=a[i]<=10^7 。

Source

 

Solution

可持久化trie……写法和主席树差不多。

首先定义一个bi为前i个数字的异或和,询问max(b[n]^x^b[p]) l ≤ p ≤ r。

把b数组插入到trie中,查询的时候很容易想到贪心的做法。

在数组前放一个0,会更好处理