P4462 [CQOI2018] 异或序列
题目描述
给定一个长度为 n 的整数数列 {a1,a2,…,an}、一个整数 k,以及 m 次询问。
每次询问给出两个整数 l 和 r,请你求出区间 [l,r] 内有多少个连续子区间满足异或和等于 k。也就是说,求出满足 l≦x≦y≦r 且 ax⊕ax+1⊕⋯⊕ay=k 的整数对 (x,y) 的数量。
其中 ⊕ 表示按位异或运算。
输入格式
第一行输入三个整数 $n, m, k \left(1 \leqq n, m \leqq 10^5;\ 0 \leqq k \leqq 10^5\right)$ 代表数列长度、询问次数和异或和参数。
第二行输入 n 个整数 $a_1, a_2, \dots, a_n \left(0 \leqq a_i \leqq 10^5\right)$ 代表数列中的元素。
此后 m 行,第 t 行输入两个整数 $l_t, r_t \left(1 \leqq l_t \leqq r_t \leqq n\right)$ 代表第 t 次询问的区间。
输出格式
输出 m 行,第 t 行输出一个整数,代表第 t 次询问中满足条件的连续子区间个数。
测试样例
4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4
4
2
1
2
1
样例 1 解释
数列为 {1,2,3,1},k=1,共有 5 次询问。
对于第 1 次询问 [1,4],区间内所有连续子区间的异或和如下:
∙长度为 1 的子区间:[1,1] 的异或和为 1,[2,2] 的异或和为 2,[3,3] 的异或和为 3,[4,4] 的异或和为 1,其中 [1,1] 和 [4,4] 满足条件;
∙长度为 2 的子区间:[1,2] 的异或和为 1⊕2=3,[2,3] 的异或和为 2⊕3=1,[3,4] 的异或和为 3⊕1=2,其中 [2,3] 满足条件;
∙长度为 3 的子区间:[1,3] 的异或和为 1⊕2⊕3=0,[2,4] 的异或和为 2⊕3⊕1=0,都不满足条件;
∙长度为 4 的子区间:[1,4] 的异或和为 1⊕2⊕3⊕1=1,满足条件。
因此第 1 次询问的答案为 4。其余询问同理:
∙第 2 次询问 [1,3]:满足条件的子区间为 [1,1] 和 [2,3],答案为 2;
∙第 3 次询问 [2,3]:满足条件的子区间为 [2,3],答案为 1;
∙第 4 次询问 [2,4]:满足条件的子区间为 [2,3] 和 [4,4],答案为 2;
∙第 5 次询问 [4,4]:满足条件的子区间为 [4,4],答案为 1。
6 4 2
1 3 1 2 3 1
1 6
2 5
1 3
4 6
6
2
2
2
样例 2 解释
数列为 {1,3,1,2,3,1},k=2,共有 4 次询问。
∙第 1 次询问 [1,6]:满足条件的子区间为 [1,2]、[2,3]、[4,4]、[5,6]、[1,5] 和 [2,6],异或和依次为 2,2,2,2,2,2,答案为 6;
∙第 2 次询问 [2,5]:满足条件的子区间为 [2,3] 和 [4,4],答案为 2;
∙第 3 次询问 [1,3]:满足条件的子区间为 [1,2] 和 [2,3],答案为 2;
∙第 4 次询问 [4,6]:满足条件的子区间为 [4,4] 和 [5,6],答案为 2。
提示
对于 30% 的数据,1≦n,m≦103。
对于 100% 的数据,1≦n,m≦105,0≦k≦105,0≦ai≦105,1≦lt≦rt≦n。