CF-Div2-832 D. Yet Another Problem(bitmask&结论)

CF-Div2-832 D. Yet Another Problem(bitmask&结论)

为了方便设每次询问$[l,r]$ 的长度为$n$。

注意到：

每次操作不会影响$Xor(l,r)$的结果。

所以必要条件1：$Xor(l,r)=0$
然后我们可以发现，我们可以将从$l$开始的前缀异或和分为两个部分，长度为奇数的前缀和长度为偶数的。

每次操作后，比如我们对$[x,y],l\le x\le y\le r$ 操作。

那么下标在$[l,x-1]$ 和$[y+1,r]$ 的下标前缀答案不会改变。

而下标在$[x,y]$之间的前缀异或和结果要么是$Xor(l,y)$ 要么$Xor(l,x-1)$

也就是说这两个集合不会相互影响，且每次操作只会使集合大小非递增。

因此要想最终$Xor(l,r)=0$，显然这两个集合都必须包含前缀异或和为$0$的下标。

更进一步，对于区间$1\le l\le r\le n$，显然$Xor(l,r)=0$ 而且必须存在

$Xor(1,r)=Xor(1,x),x\mathrm{mod}2\ne r\mathrm{mod}2$

那么$Xor(l,r)=Xor(x+1,r)=Xor(l,x)=0$

不满足必要条件1，无解。

如果区间全为0，答案为0.

如果$len(l,r)$为奇数，答案为1。

否则如果$a[l]=0||a[r]=0$ 则可以转情况2，答案为1.

否则如果$las{t}_r\ge l$ 保证$[las{t}_l+1,r]$ 异或和为0。操作次数为2。

否则无解。

int _runtimeTerror_()
{
    int n, Q;
    cin >> n >> Q;
    map<int, int> odd, even;
    vector<int> last_nz(n + 1, 0), last(n + 1, -1), pxor(n + 1, 0);
    vector<int> a(n + 1);
    even[0] = 0;
    int cur = 0;
    for(int i=1;i<=n;++i) {
    	cin >> a[i];
    	cur ^= a[i];
    	pxor[i] = cur;
    	if(a[i] == 0) {
    		last_nz[i] = last_nz[i - 1];
    	}
    	else {
    		last_nz[i] = i;
    	}
    	if(i & 1) {
    		if(even.count(cur)) {
    			last[i] = even[cur];
    		}
    		odd[cur] = i;
    	}
    	else {
    		if(odd.count(cur)) {
    			last[i] = odd[cur];
    		}
    		even[cur] = i;
    	}
    }
    while(Q--) {
    	int l, r;
    	cin >> l >> r;
    	if(pxor[l - 1] != pxor[r]) {
    		cout << "-1\n";
    	}
    	else if(last_nz[r] < l) {
    		cout << "0\n";
    	}
    	else if(r % 2 == l % 2) {
    		cout << "1\n";
    	}
    	else if(a[l] == 0 or a[r] == 0) {
    		cout << "1\n";
    	}
    	else if(last[r] >= l) {
    		cout << "2\n";
    	}
    	else {
    		cout << "-1\n";
    	}
    }
    return 0;
}

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