原题链接：

Problem - D - Codeforces

题目描述：

You are given an array aa of nn integers a1,a2,a3,…,ana1,a2,a3,…,an.

You have to answer qq independent queries, each consisting of two integers ll and rr.

• Consider the subarray a[l:r]a[l:r] == [al,al+1,…,ar][al,al+1,…,ar]. You can apply the following operation to the subarray any number of times (possibly zero)-
  1. Choose two integers LL, RR such that l≤L≤R≤rl≤L≤R≤r and R−L+1R−L+1 is odd.
  2. Replace each element in the subarray from LL to RR with the XOR of the elements in the subarray [L,R][L,R].
• The answer to the query is the minimum number of operations required to make all elements of the subarray a[l:r]a[l:r] equal to 00 or −1−1 if it is impossible to make all of them equal to 00.

You can find more details about XOR operation here.

Input

The first line contains two integers nn and qq (1≤n,q≤2⋅105)(1≤n,q≤2⋅105)  — the length of the array aa and the number of queries.

The next line contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai<230)(0≤ai<230)  — the elements of the array aa.

The ii-th of the next qq lines contains two integers lili and riri (1≤li≤ri≤n)(1≤li≤ri≤n)  — the description of the ii-th query.

Output

For each query, output a single integer  — the answer to that query.

题目大意：

给定一个长度为n的非负整数数组，每次询问给出L和R，用户每次可以进行的操作是在子数组[L,R]内选择一个奇数长度的子数组[l,r]，使得[l,r]内的所有数变成[l,r]的异或和。问有没有可能在若干次操作后使得整个子数组[L,R]全0。求最小操作次数，如果不可能完成则输出-1。

解题思路：

异或有加法性质，所以我们可以用前缀和的方式来处理异或和。

操作一段异或和为0的子区间使得这个子区间变为全0并不会让它的父区间异或和发生改变，所以如果本身父区间的异或和就不为0，那么无解。

下面分类讨论[L,R]异或和为0的几种情况：

1、[L,R]本身就是全0，不需要操作，答案为0.

2、[L,R]长度为奇数，那么直接操作整个区间即可，答案为1.

3、[L,R]长度为偶数，如果a[L]是0，我们操作[L+1,R]，如果a[R]是0，那么我们操作[L,R-1]，即：a[L]和a[R]至少一个是0，答案为1。（因为已知[L,R]的异或和为0，那么如果a[L]和a[R]其中一个为0，剩下的子区间异或肯定也是0）。

4、[L,R]长度为偶数，区间内有奇数长度的子区间前缀异或和为0，那么先操作这个奇数长度的子区间，再操作剩余的另一段子区间即可。答案为2。（[L,R]异或和为0，其中一段子区间异或和也为0，那么另一段子区间异或和肯定也为0）。

5、其他情况，无解。

代码（CPP）：

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
typedef unsigned long long ull;
const int maxn = 2e5 + 10;
const int INF = 0x3fffffff;
int n, q, a[maxn], XOR[maxn], sum[maxn], pre[maxn];  // pre[i]=j：XOR[i]==XOR[j-1]
map<int, int> last[2]; // last[0]存放i为偶数的每个XOR值最后出现的位置，last[1]存放i为奇数的……

// 查询前缀异或和
int queryXOR(int l, int r)
{
    return XOR[r] ^ XOR[l - 1];
}

// 查询前缀和
int querySum(int l, int r)
{
    return sum[r] - sum[l - 1];
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(18);

    cin >> n >> q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        XOR[i] = XOR[i - 1] ^ a[i];
        sum[i] = sum[i - 1] + a[i];
        // 区间长为奇数，那么区间端点下标同奇或同偶
        // [l,r]异或和为0，那么有XOR[l - 1] == XOR[r]
        if(last[!(i & 1)].count(XOR[i]))  // 注意是要取反的，因为这里求的其实是对每个r, 最近的l - 1的位置而不是l
        {
            pre[i] = last[!(i & 1)][XOR[i]] + 1;  // 注意要加1
        }
        last[i & 1][XOR[i]] = i;
    }
    while (q--)
    {
        int l, r, ans = -1;
        cin >> l >> r;
        if (!queryXOR(l, r)) // 必须是区间内的异或和为0才可能有解
        {
            if (!querySum(l, r)) // 如果区间本就是全0
                ans = 0;
            else if ((r - l + 1) & 1) // 如果区间长度就是奇数
                ans = 1;
            else
            {
                if (!a[l] || !a[r]) // 如果区间长度为偶数，然后左右端点至少其中一个为0
                    ans = 1;
                else if (pre[r] >= l) // 区间内有奇数长度的子区间前缀异或和为0
                    ans = 2;
            }
        }
        cout << ans << endl;
    }
    return 0;
}