主题

主题

 
   

2741: 【FOTILE模拟赛】L

原题:http://www.lydsy.com/JudgeOnline/problem.php?id=2741

Description

FOTILE得到了一个长为N的序列A,为了拯救地球,他希望知道某些区间内的最大的连续XOR和。

即对于一个询问,你需要求出max(Ai xor Ai+1 xor Ai+2 ... xor Aj),其中l<=i<=j<=r。

为了体现在线操作,对于一个询问(x,y):

l = min ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).

r = max ( ((x+lastans) mod N)+1 , ((y+lastans) mod N)+1 ).

其中lastans是上次询问的答案,一开始为0。

Input

第一行两个整数N和M。

第二行有N个正整数,其中第i个数为Ai,有多余空格。

后M行每行两个数x,y表示一对询问。

Output

共M行,第i行一个正整数表示第i个询问的结果。

Sample Input

3 3

1 4 3

0 1

0 1

4 3

Sample Output

5

7

7

HINT

N=12000,M=6000,x,y,Ai在signed longint范围内。


个人解法:

自然可以想到区间异或和转换为前缀异或和。之后变为了查找区间内两个数字的最大异或和。

如果可以离线操作的话,我们可以先排序,再直接在Trie树上面搞事情就好了。

(所以可以二进制分组?本蒟这么菜自然不会)

然后我们发现没有修改操作。

于是我们可以分块预处理。

如果我们预处理出了第i块到第j块这一部分区间的两个数字异或和最大值,且知道了每个点与任意区间的数字异或的最大值(这样就可以扫描剩余非整块的部分),就可以求出答案了。

然后就想到建一棵可持久化Trie树。

预处理的部分,可以考虑区间DP的方法。


代码如下:

https://code.csdn.net/snippets/2212871


发现自己也可以独立一下子就思考出一道分块题了。

果然要学会套路。

 
 
评论