【分类讨论】CF1747D

【分类讨论】CF1747D

Problem - D - Codeforces

题意

思路

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

先判无解

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

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

之后怎么讨论

注意到需要讨论区间长度

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

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

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

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

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

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

Code：

#include <bits/stdc++.h>#define int long longconstexpr 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;
}