P4462 [CQOI2018] XOR Sequence

Given an integer sequence $a_1, a_2, \dots, a_n$ of length $n$, for a query with parameters $l, r$, ask how many subarrays within $a_l, a_{l+1}, \dots, a_r$ have xor-sum equal to $k$. That is, among all $x, y$ such that $(l \leq x \leq y \leq r)$, how many pairs $(x, y)$ satisfy $a_x \oplus a_{x+1} \oplus \dots \oplus a_y = k$.

The first line contains three integers $n, m, k$. The second line contains $n$ integers separated by spaces, namely $a_1, a_2, \dots, a_n$. Each of the next $m$ lines contains two integers $l_j$ and $r_j$, representing one query.

Output $m$ lines, each corresponding to the answer for one query.

For $30\%$ of the testdata, $1 \leq n, m \leq 1000$. For $100\%$ of the testdata, $1 \leq n, m \leq 10^5$, $0 \leq k, a_i \leq 10^5$, $1 \leq l_j \leq r_j \leq n$. Translated by ChatGPT 5