#P2741. 【FOTILE模拟赛】L

    ID: 1847 传统题 1000ms 162MiB 尝试: 4551 已通过: 756 难度: 7 上传者: 标签>CF2300提高+/省选-异或前缀和可持久化 Trie前缀版本作差最大异或查询按位贪心根号分块Byseter

【FOTILE模拟赛】L

题目描述

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

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

max⁡l≤i≤j≤r⨁k=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。

输入格式

第一行两个整数 NN 和 MM。 第二行有 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=12000,M=6000M=6000,x,y,Aix,y,A_i 在 signed long int 范围内。

题目来源

By seter