【分类讨论】CF1747D

╰+哭是因爲堅強的太久メ 2024-02-21 10:21 50阅读 0赞

[Problem - D - Codeforces][]

题意

![15419b0d442b493ea690e2fc2dfe31e4.png][]

思路

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

先判无解

显然，如果区间异或和不是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 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;
    }

[Problem - D - Codeforces]: https://codeforces.com/contest/1747/problem/D
[15419b0d442b493ea690e2fc2dfe31e4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/21/13ed189ec43d40cc91282acb5d449dfa.png