【分类讨论】CF1747D

Problem - D - Codeforces

题意

思路

一看这个做法一定就是分类讨论

先判无解

显然，如果区间异或和不是0一定无解

如果区间内全是0，答案一定是0

之后怎么讨论

注意到需要讨论区间长度

如果长度是奇数，那么直接操作即可，答案一定是1

else 如果是偶数，需要看是否存在一个分割点使得一个区间可以分割成两个区间，两个区间的区间异或和都是0

这点有点难注意到，我们很容易地会以为如果一个区间的异或和是0，一定存在分割点，其实不一定，这点需要记住

那么问题就是如何找这个分割点

这个分割点假设是 k, 需要满足pre[l - 1] == pre[k] 且 位置的奇偶性要和 l 一致，因为区间长度要是奇数，那么就是去找后面第一个满足这个条件的就行

那么就是把所有前缀异或和为 pre[l - 1]和位置的奇偶性放进集合里，二分查找即可

Code：

#include 
 
#define int long long
 
constexpr int N = 2e5 + 10;
constexpr int mod = 998244353;
 
std::map<int, std::vector<int> > S[2];
 
int n, q;
int a[N];
int pre[N];
int s[N];
 
int get(int l, int r) {
	return pre[r] ^ pre[l - 1];
}
void solve() {
	std::cin >> n >> q;
	pre[0] = 0;
	for (int i = 1; i <= n; i ++) {
		std::cin >> a[i];
		pre[i] = pre[i - 1] ^ a[i];
		s[i] = s[i - 1] + (a[i] == 0);
		S[i & 1][pre[i]].push_back(i);
	}
	while(q --) {
		int l, r;
		std::cin >> l >> r;
		if (get(l, r) != 0) {
			std::cout << -1 << "\n";
			continue;
		}
		if (s[r] - s[l - 1] == r - l + 1) {
			std::cout << 0 << "\n";
			continue;
		}
		if ((r - l + 1) % 2 == 1 ||((r - l + 1) % 2 == 0 && (a[l] == 0 || a[r] == 0))) {
			std::cout << 1 << "\n";
		}else {
			auto it = std::lower_bound(S[l & 1][pre[l - 1]].begin(), S[l & 1][pre[l - 1]].end(), l);
			if (it != S[l & 1][pre[l - 1]].end() && *it < r) {
				std::cout << 2 << "\n";
			}else {
				std::cout << -1 << "\n";
			}
		}
	}
}
signed main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
 
	int t = 1;
	while (t--) {
		solve();
	}
	return 0;
}