4291. [CQOI2018] 异或序列

【题目背景】

在计算机科学中，异或操作是一种常见的位运算，常用于加密、校验和数据压缩等领域。本题源于对序列中子区间异或和的研究，是异或性质与区间查询的经典应用。

【题目描述】

已知一个长度为 $n$ 的整数数列 $a_1,a_2,\dots,a_n$，给定查询参数 $l,r$，问在 $a_l,a_{l+1},\dots,a_r$ 区间内，有多少子区间满足异或和等于 $k$。也就是说，对于所有的 $x,y (l \leq x \leq y \leq r)$，能够满足 $a_x \oplus a_{x+1} \oplus \dots \oplus a_y = k$ 的 $x,y$ 有多少组。

【输入格式】

输入文件第一行，为 $3$ 个整数 $n,m,k$。 

第二行为空格分开的 $n$ 个整数，即 $a_1,a_2,..a_n$。 

接下来 $m$ 行，每行两个整数 $l_j,r_j$，表示一次查询。

【输出格式】

输出文件共 $m$ 行，对应每个查询的计算结果。

【样例输入】

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

【样例输出】

4
2
1
2
1

【样例说明】

样例中，序列为 $[1,2,3,1]$，$k=1$。

 - 查询 $[1,4]$：

满足条件的子区间有 $(1,1),(3,3),(4,4),(3,4)$，共 $4$ 组。

 - 查询 $[1,3]$：

满足条件的子区间有 $(1,1),(3,3)$，共 $2$ 组。

 - 查询 $[2,3]$：

满足条件的子区间有 $(3,3)$，共 $1$ 组。 

- 查询 $[2,4]$：

满足条件的子区间有 $(3,3),(4,4)$，共 $2$ 组。 

- 查询 $[4,4]$：

满足条件的子区间有 $(4,4)$，共 $1$ 组。

【数据规模与约定】

对于 $30\%$ 的数据，$1 \leq n, m \leq 1000$。 

对于 $100\%$ 的数据，$1 \leq n, m \leq 10^5$，$0 \leq k, a_i \leq 10^5$，$1 \leq l_j \leq r_j \leq n$。

【来源】

CQOI 2018