bzoj#P2741. 【FOTILE模拟赛】L

【FOTILE模拟赛】L

题目描述

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

即对于一个询问,你需要求出

maxlijrk=ijak\max_{l\le i\le j\le r}\bigoplus_{k=i}^{j} a_k

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

  • $l = \min ( ((x+{\rm lastans}) \bmod N)+1 , ((y+{\rm lastans}) \bmod N)+1)$.
  • $r = \max ( ((x+{\rm lastans}) \bmod N)+1 , ((y+{\rm lastans}) \bmod N)+1)$.

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

输入格式

第一行两个整数 NNMM。 第二行有 NN 个正整数,其中第 ii 个数为 AiA_i,有多余空格。 后M行每行两个数 x,yx,y 表示一对询问。

输出格式

MM 行,第 ii 行一个正整数表示第 ii 个询问的结果。

3 3
1 4 3
0 1
0 1
4 3

5
7
7

提示

HINT N=12000N=12000M=6000M=6000x,y,Aix,y,A_isigned long int 范围内。

题目来源

By seter