D. Yet Another Problem（异或/位运算/二分）

题目

题意

给定n个数a，q个查询，对于每次查询，给定下标1<=l<=r<=n，

问经过若干以下操作，能否使得a[l],a[l+1],…,a[r]全部变成0

• 选择区间l<=L,R<=r，
• 选择的区间，长度一定要为奇数
• 将区间[L,R]所有元素，更新为它们的异或和，即a[L]=a[L+1]=…a[R]=a[L]^a[L+1]^…^a[R]

问，需要经过最少多少次操作，才能使a[l],a[l+1],…,a[r]全部变成0。如果不能使a[l],a[l+1],…,a[r]全部变成0，则输出-1

思路

每次操作，不影响区间[l,r]的异或和。

• 如果a[l]^a[l+1]^…^a[r]不等于0，此时显然无解
• 如果查询的区间，所有元素为0，此时有解，操作次数为0
• 如果查询的区间长度为奇数，此时只需要整个区间异或1次

现在考虑区间长度为偶数的场景。

观察操作后的异或前缀和，定义s为数组的异或前缀和元素集合。
那么经过一次操作后，得到的新集合s’ 元素只减不增，即s’是s的子集。

要使得最终所有元素为0，即最终s’={0}，则要求原来的前缀和集合s包含0。

因此，我们可以维护下标为奇数的和下标为偶数的异或前缀和，对应的下标数组。
对于每次查询，查询和l-1奇偶性相同的前缀和下标中，是否存在对应的下标j，使得a[l]^a[l+1]^…^a[j]==0
如果能找到，我们只需选择区间[l,j]，[j+1,r]，执行2次操作，即可。

特判下，a[l]为0和a[r]为0的情况。

详见代码

代码

#include 
using namespace std;
#define ll long long
#define pcc pair<char, char>
#define pii pair<int, int>
#define inf 0x3f3f3f3f
const int maxn = 200010;
const int mod = 998244353;


int n, q;
int a[maxn];
map<int, vector<int>> mp[2];
int b[maxn];
ll sum[maxn];
int l, r;

void solve() {
    scanf("%d%d", &n, &q);
    sum[0] = 0;
    for (int i = 1; i <= n; ++i) {
    	scanf("%d", &a[i]);
    	b[i] = b[i-1] ^ a[i];
    	mp[i&1][b[i]].push_back(i);
    	sum[i] = sum[i-1] + a[i];
	}
	
	while (q--) {
		scanf("%d%d", &l, &r);
		int len = r - l + 1;
		if (b[l-1] ^ b[r]) { // a[l]^...^a[r] != 0
			printf("-1\n");
			continue;
		}
		
		int res = -1;
		if (sum[r] - sum[l-1] == 0) { // a[l] =... = a[r] = 0
			res = 0;
		} else if ((len & 1) || (!a[l] || !a[r])) {
			res = 1;
		} else {
			vector<int> &ve = mp[l&1][b[l-1]];
			int idx = lower_bound(ve.begin(), ve.end(), l) - ve.begin();
			if (idx < ve.size() && ve[idx] <= r) {
				res = 2;
			}
		}
		printf("%d\n", res);
		
	}
}
int main() {
    int t = 1;
//    scanf("%d", &t);
    int cas = 1;
    while (t--) {
//		printf("cas %d:\n", cas++);
        solve();
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61