#P8257. [CTS2022] 普罗霍洛夫卡

[CTS2022] 普罗霍洛夫卡

题目描述

给定序列 a1,,ana_1,\dots,a_n,共 mm 次询问,每次询问给出 l,rl,r,查询所有满足 lLRrl\le L\le R\le r(L,R)(L,R) 的权值的按位异或和,二元组 (L,R)(L,R) 的权值是 {aiLiR}|\{a_i\mid L\le i\le R\}|

输入格式

从标准输入读入数据。

第一行两个整数 n mn\ m

接下来一行 nn 个整数 a1,,ana_1,\dots,a_n

接下来 mm 行,每行两个整数 l rl\ r 表示一次查询。

输出格式

输出到标准输出。

输出 mm 行,依次表示每个询问的答案。

5 2
1 1 1 2 4
1 5
3 5

3
2

提示

对于 5%5\% 的数据,满足 1n,m1001\le n,m\le 100

对于 10%10\% 的数据,满足 1n,m50001\le n,m\le 5000

对于 20%20\% 的数据,满足 1n,m1051\le n,m\le 10^5

对于 30%30\% 的数据,满足 1n,m2×1051\le n,m\le 2\times 10^5

对于 40%40\% 的数据,满足 1n,m3×1051\le n,m\le 3\times 10^5

对于 50%50\% 的数据,满足 1n,m3.5×1051\le n,m\le 3.5\times 10^5

对于另外 10%10\% 的数据,满足 m=n2m=n^2

对于另外 10%10\% 的数据,满足对任意 i=1ni=1\cdots nai2a_i\le 2

对于另外 10%10\% 的数据,满足对任意 i=1ni=1\cdots nai10a_i\le 10

对于 100%100\% 的数据,满足 1n,m4×1051\le n,m\le 4\times 10^51ain1\le a_i\le n,所有数值为整数。

每类数据构成子任务。