Equal XOR Segments
Contest: Codeforces Round 943 (Div. 3)
Difficulty rating: 1800
Tags: binary search, data structures

Let us call an array $$$x_1,\dots,x_m$$$ interesting if it is possible to divide the array into $$$k>1$$$ parts so that bitwise XOR of values from each part are equal.

More formally, you must split array $$$x$$$ into $$$k$$$ consecutive segments, each element of $$$x$$$ must belong to exactly $$$1$$$ segment. Let $$$y_1,\dots,y_k$$$ be the XOR of elements from each part respectively. Then $$$y_1=y_2=\dots=y_k$$$ must be fulfilled.

For example, if $$$x = [1, 1, 2, 3, 0]$$$, you can split it as follows: $$$[\color{blue}1], [\color{green}1], [\color{red}2, \color{red}3, \color{red}0]$$$. Indeed $$$\color{blue}1=\color{green}1=\color{red}2 \oplus \color{red}3\oplus \color{red}0$$$.

You are given an array $$$a_1,\dots,a_n$$$. Your task is to answer $$$q$$$ queries:

- For fixed $$$l$$$, $$$r$$$, determine whether the subarray $$$a_l,a_{l+1},\dots,a_r$$$ is interesting.

Input format:
The first line contains a single integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$2 \le n \le 2 \cdot 10^5$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of elements in the array and the number of queries respectively.

The next line contains $$$n$$$ integers $$$a_1,\dots,a_n$$$ ($$$0 \le a_i < 2^{30}$$$) — elements of the array.

Each of the next $$$q$$$ lines contains two integers $$$l$$$ and $$$r$$$ ($$$1 \le l < r \le n$$$) describing the query.

It is guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

It is guaranteed that the sum of $$$q$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each query, output "YES" if the subarray is interesting and "NO" otherwise.

You can output "Yes" and "No" in any case (for example, the strings "yES", "yes", and "Yes" will be recognized as correct answers).

Constraints:
Time limit: 5.0 s
Memory limit: 256.0 MB

Note:
Explanation for the first test case:

The first query is described in the statement.

In the second query, we should divide $$$[1,2,3]$$$. A possible division is $$$[1,2],[3]$$$, since $$$1\oplus 2=3$$$.

It can be shown that for queries $$$3,4,5$$$, the subarrays are not interesting.

Example input:
4
5 5
1 1 2 3 0
1 5
2 4
3 5
1 3
3 4
5 5
1 2 3 4 5
1 5
2 4
3 5
1 3
2 3
7 4
12 9 10 9 10 11 9
1 5
1 7
2 6
2 7
11 4
0 0 1 0 0 1 0 1 1 0 1
1 2
2 5
6 9
7 11

Example output:
YES
YES
NO
NO
NO

YES
NO
NO
YES
NO

NO
NO
NO
NO

YES
NO
YES
YES

Editorial:
Observation: any division on more than $$$k>3$$$ segments can be reduced to at most $$$3$$$ segments.
Proof: suppose the XORs of elements from the segments are $$$x_1,\dots,x_k$$$. The condition $$$x_1=x_2=\dots=x_k$$$ must be fulfilled. If $$$k>3$$$ we may take any three consecutive segments and merge them into one, because $$$x\oplus x\oplus x=x$$$. In such way, we reduce $$$k$$$ by two. We may repeat this process while $$$k>3$$$.
Let us construct an array $$$b_1=a_1$$$ and $$$b_i=b_{i-1}\oplus a_i$$$ for $$$i\geq 2$$$. Now, $$$a_l\oplus a_{l+1}\oplus \dots \oplus a_r=b_r\oplus b_{l-1}$$$.
There are two cases:
• $$$k=2$$$, meaning that we divide the segment $$$[l,r]$$$ into two segments. Suppose the segments are $$$[l,m]$$$ and $$$[m+1,r]$$$. In such case we must check if $$$b_m\oplus b_{l-1}=b_{r}\oplus b_m$$$. This equality reduces to $$$b_{l-1}=b_r$$$.
• $$$k=3$$$, meaning that we divide segment $$$[l,r]$$$ into $$$[l,s]$$$, $$$[s+1,t]$$$ and $$$[t+1,r]$$$. We must check if $$$b_s\oplus b_{l-1}=b_{t}\oplus b_s$$$ and $$$b_s \oplus b_{t}=b_r \oplus b_{t}$$$. It is equivalent to check if $$$b_{l-1}=b_t$$$ and $$$b_s=b_r$$$. Also, $$$s<t$$$ must be fulfilled. Hence, we may find the largest $$$t < r$$$ that $$$b_t=b_{l-1}$$$ and the minimal $$$s\geq l$$$ that $$$b_s=b_r$$$. It can be done using binary search on the positions of a certain value.