D. Yet Another Problem

原题链接：Problem - D - Codeforces

题意：给定一个长度为n的数组，给定m个独立询问。每个询问包含[l, r]，要求每次在[l, r]范围内选择若干个奇数长度的连续区间使得这段区间内所有值变成区间异或和，求最少操作次数使得[l, r]内所有元素的值变为0。

思路：

以下结论按序号依次判断输出

一、 首先，若该区间的异或和不为0，则输出-1。

解释：因为我们只能选择长度为奇数的区间，并且将区间内所有的值变成区间异或和的值，也就是说，经过一次操作之后，该奇数长度的区间内的值都是相等的。但除全是0外，奇数个相同数字的异或和不可能为0，比如偶数个1的异或和为0，但是奇数个1的异或和为1。

二、显而易见，若该区间内的所有数都为0，那么操作数为0。（不把二结论放在一结论之前判断是因为若区间异或和不为0，那么该区间肯定不是全为0）

三、既然不满足一结论和二结论，说明了该区间异或和为0并且区间内元素不全为0，所以若该区间的区间长度为奇数，我们直接选择全部的这个区间就行了，这样的操作数为1。

四、若该区间的长度为偶数

1、若该区间的左端点为0或者右端点为0，则输出1。因为0对于异或和是没有影响的，所以我们可以抛弃一端元素为0的端点，使得选择区间长度为奇数。

2、选择两个区间长度为奇数的区间，判断前缀异或和是否为0，若为0则可以选择该择区间并且选择剩下的区间，使得异或和为0。

解释1：为什么是选两次而不是四次六次？例如，将区间长度为12的区间分成了3-3-3-3这样的四个子区间，若这样每个区间的异或和为0,那么我们完全可以选择第一个区间为一组，第二、三、四个区间位一组，这两组区间的异或和也是0，这四个区间的异或和表示0-0-0-0，分完组后这两组的异或和表示为0-0，它们的异或和还是0，我们最多选择两次就足够了。

解释2：为什么前缀异或和为0了它剩下区间的异或和也为0？因为异或是不进位的加法，所以若一个区间的异或和为0，那么每个数各个二进制的位数上的1的个数必须为偶数，所以若一整个区间各个二进制的位数上的1的个数为偶数，并且选择了一个区间各个二进制的位数上的1的个数为偶数，那么剩下的那个区间的各个二进制的位数上的1的个数也肯定为偶数，它的异或和肯定为0。

五、其它情况输出-1。

说完了结论，还有最关键的一步：代码实现。

该题代码最主要的就是优化查询区间内前缀和为0的端点。我们设使得前缀异或和为0的下标为x，区间左端点为l，那么SumXor[x]==SumXor[l-1]，因为这样SumXor[x]^SumXor[l-1]的值才为0，也就是区间[l,x]的异或和为0。所以我们将区间异或和相同，并且下标奇偶性相同的前缀异或和元素存入map，这样在查询等于SumXor[l-1]并且下标奇偶性与l不同的下标时，就能使用二分查找函数有效减少时间复杂度。

#define _CRT_SECURE_NO_WARNINGS 1
#include 
#include 
#include 
#include 
#include
#include
#include
#include
#include
#define FOR(a,b) for(int i=a;i<=b;i++)
#define ROF(a,b) for(int i=a;i>=b;i--)
#define FORj(a,b) for(int j=a;j<=b;j++)
#define ROFj(a,b) for(int j=a;j>=b;j--)
#define FORk(a,b) for(int k=a;k<=b;k++)
#define ROFk(a,b) for(int k=a;k>=b;k--)
#define mem(i,a) memset(i,a,sizeof(i))
#define ll long long
#define inf 0x3f3f3f3f
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define int  long long
#define endl '\n'
#define yes cout<<"YES"<
#define no cout<<"NO"<
#define pi acos(-1.0)
using namespace std;
const int maxn = 5e6 + 5;
int a[maxn],sum[maxn],cnt[maxn];
void solve() {
	map<int, vector<int>>j,o;
	int n, q;
	cin >> n >> q;
	FOR(1, n) {
		cin >> a[i];
		sum[i] = sum[i - 1] ^ a[i];
		cnt[i] = cnt[i - 1] + (a[i] == 0);
		if (i & 1)j[sum[i]].push_back(i);
		else o[sum[i]].push_back(i);
	}
	while (q--) {
		int l, r;
		cin >> l >> r;
		if (sum[r] ^ sum[l - 1])cout << -1 << endl;
		else if (cnt[r]-cnt[l-1] == r - l + 1)cout << 0 << endl;
		else if((l-r+1)%2) cout<<1<
		else if((l-r+1)%2==0) {
			if (a[l] == 0 || a[r] == 0)cout << 1 << endl;
			else if (l & 1) {
				auto it = lower_bound(j[sum[l - 1]].begin(), j[sum[l - 1]].end(), l);
				if (it != j[sum[l - 1]].end() && *it <= r) 	cout << 2 << endl;
				else cout<<-1<
			} else if (!(l & 1)) {
				auto it = lower_bound(o[sum[l - 1]].begin(), o[sum[l - 1]].end(), l);
				if (it != o[sum[l - 1]].end() && *it <= r) 	cout << 2 << endl;
				else cout << -1 << endl;
			}
		}
	}
}
signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);
	//int _;
	//cin >> _;
	//while (_--)
	solve();
	return 0;
}