LG#P4462. [CQOI2018] 异或序列

[CQOI2018] 异或序列

P4462 [CQOI2018] 异或序列

题目描述

\hspace{15pt}给定一个长度为 nn 的整数数列 {a1,a2,…,an}\{a_1, a_2, \dots, a_n\}、一个整数 kk,以及 mm 次询问。

\hspace{15pt}每次询问给出两个整数 ll 和 rr,请你求出区间 [l,r][l, r] 内有多少个连续子区间满足异或和等于 kk。也就是说,求出满足 l≦x≦y≦rl \leqq x \leqq y \leqq r 且 ax⊕ax+1⊕⋯⊕ay=ka_x \oplus a_{x+1} \oplus \dots \oplus a_y = k 的整数对 (x,y)(x, y) 的数量。

\hspace{15pt}其中 ⊕\oplus 表示按位异或运算。

输入格式

\hspace{15pt}第一行输入三个整数 $n, m, k \left(1 \leqq n, m \leqq 10^5;\ 0 \leqq k \leqq 10^5\right)$ 代表数列长度、询问次数和异或和参数。

\hspace{15pt}第二行输入 nn 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 10^5\right)$ 代表数列中的元素。

\hspace{15pt}此后 mm 行,第 tt 行输入两个整数 $l_t, r_t \left(1 \leqq l_t \leqq r_t \leqq n\right)$ 代表第 tt 次询问的区间。

输出格式

\hspace{15pt}输出 mm 行,第 tt 行输出一个整数,代表第 tt 次询问中满足条件的连续子区间个数。

测试样例

4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4
4
2
1
2
1

样例 1 解释

\hspace{15pt}数列为 {1,2,3,1}\{1, 2, 3, 1\},k=1k = 1,共有 55 次询问。

\hspace{15pt}对于第 11 次询问 [1,4][1, 4],区间内所有连续子区间的异或和如下:

∙ \hspace{23pt}\bullet\,长度为 11 的子区间:[1,1][1,1] 的异或和为 11,[2,2][2,2] 的异或和为 22,[3,3][3,3] 的异或和为 33,[4,4][4,4] 的异或和为 11,其中 [1,1][1,1] 和 [4,4][4,4] 满足条件;

∙ \hspace{23pt}\bullet\,长度为 22 的子区间:[1,2][1,2] 的异或和为 1⊕2=31 \oplus 2 = 3,[2,3][2,3] 的异或和为 2⊕3=12 \oplus 3 = 1,[3,4][3,4] 的异或和为 3⊕1=23 \oplus 1 = 2,其中 [2,3][2,3] 满足条件;

∙ \hspace{23pt}\bullet\,长度为 33 的子区间:[1,3][1,3] 的异或和为 1⊕2⊕3=01 \oplus 2 \oplus 3 = 0,[2,4][2,4] 的异或和为 2⊕3⊕1=02 \oplus 3 \oplus 1 = 0,都不满足条件;

∙ \hspace{23pt}\bullet\,长度为 44 的子区间:[1,4][1,4] 的异或和为 1⊕2⊕3⊕1=11 \oplus 2 \oplus 3 \oplus 1 = 1,满足条件。

\hspace{15pt}因此第 11 次询问的答案为 44。其余询问同理:

∙ \hspace{23pt}\bullet\,第 22 次询问 [1,3][1, 3]:满足条件的子区间为 [1,1][1,1] 和 [2,3][2,3],答案为 22;

∙ \hspace{23pt}\bullet\,第 33 次询问 [2,3][2, 3]:满足条件的子区间为 [2,3][2,3],答案为 11;

∙ \hspace{23pt}\bullet\,第 44 次询问 [2,4][2, 4]:满足条件的子区间为 [2,3][2,3] 和 [4,4][4,4],答案为 22;

∙ \hspace{23pt}\bullet\,第 55 次询问 [4,4][4, 4]:满足条件的子区间为 [4,4][4,4],答案为 11。

6 4 2
1 3 1 2 3 1
1 6
2 5
1 3
4 6
6
2
2
2

样例 2 解释

\hspace{15pt}数列为 {1,3,1,2,3,1}\{1, 3, 1, 2, 3, 1\},k=2k = 2,共有 44 次询问。

∙ \hspace{23pt}\bullet\,第 11 次询问 [1,6][1, 6]:满足条件的子区间为 [1,2][1,2]、[2,3][2,3]、[4,4][4,4]、[5,6][5,6]、[1,5][1,5] 和 [2,6][2,6],异或和依次为 2,2,2,2,2,22, 2, 2, 2, 2, 2,答案为 66;

∙ \hspace{23pt}\bullet\,第 22 次询问 [2,5][2, 5]:满足条件的子区间为 [2,3][2,3] 和 [4,4][4,4],答案为 22;

∙ \hspace{23pt}\bullet\,第 33 次询问 [1,3][1, 3]:满足条件的子区间为 [1,2][1,2] 和 [2,3][2,3],答案为 22;

∙ \hspace{23pt}\bullet\,第 44 次询问 [4,6][4, 6]:满足条件的子区间为 [4,4][4,4] 和 [5,6][5,6],答案为 22。

提示

\hspace{15pt}对于 30%30\% 的数据,1≦n,m≦1031 \leqq n, m \leqq 10^3。

\hspace{15pt}对于 100%100\% 的数据,1≦n,m≦1051 \leqq n, m \leqq 10^5,0≦k≦1050 \leqq k \leqq 10^5,0≦ai≦1050 \leqq a_i \leqq 10^5,1≦lt≦rt≦n1 \leqq l_t \leqq r_t \leqq n。