【签到前缀异或和】牛客多校2023 6E

冷不防 2024-03-23 18:19 49阅读 0赞

题意：

![a5be7c6b602c4f88be59e35d4230ba23.png][]

思路：

签到签了半天，思路和正解一模一样，但是经典不会调细节

先不去考虑一个区间分为多段，先去考虑一个区间的区间和是偶数

首先很明显，我们只关注奇偶性，因此可以把所有的ai都%2，那么只剩下0和1

然后，对于一个区间，区间和为偶数，就相当于区间内1的个数是偶数

就相当于区间异或和为0

所以可以pushup一个结论：区间异或和为0 == 区间和为偶数

然后把这个结论推广，考虑两个区间 \[l1，r1\]和\[r1+1，r2\]合并的情形

对于第一个区间：cur\[r1\] == cur\[l1 - 1\]

对于第二个区间：cur\[r2\] == cur\[r1\]

因此cur\[l1 - 1\] == cur\[r1\] == cur\[r2\]

再推广，可以发现只需要关注区间内cur值等于cur\[l - 1\]有几个就完事了

那么只需要维护前缀和就行

sum\[i\]\[j\]表示前 i 个数，cur 为 j 的个数

因此需要满足 sum\[r\]\[cur\[r\]\] - sum\[l\]\[cur\[l\]\] >= k && cur\[l\] == cur\[r\]

Code：

#include <bits/stdc++.h>
    
    #define int long long
    
    using i64 = long long;
    
    using namespace std;
    
    const int N = 1e5 + 10;
    const int M = 3e6 + 10;
    const int P = 131;
    
    int a[N];
    int pre[N];
    int cur[N], sum[N][2];
    
    void solve() {
    	int n, q;
    	cin >> n >> q;
    	for (int i = 1; i <= n; i ++) {
    		cin >> a[i];
    		pre[i] = cur[i] = sum[i][0] = sum[i][1] = 0;
    		a[i] %= 2;
    	}
    
    	for (int i = 1; i <= n; i ++) {
    		cur[i] = cur[i - 1] ^ a[i];
            if (i) {
                for (int j = 0; j <= 1; j ++) {
                    sum[i][j] = sum[i - 1][j];
                }
            }
    		sum[i][cur[i]] ++;
    	}
    
    	int l, r, k;
    	while (q --) {
    		cin >> l >> r >> k;
            l --;
    		if (sum[r][cur[r]] - sum[l][cur[l]] >= k && cur[l] == cur[r]) cout <<"YES" << "\n";
    		else cout << "NO" << "\n";
    	}
    }
    signed main(){
    	ios::sync_with_stdio(false);
    	cin.tie(nullptr);
    
    	int t = 1;
    	cin >> t;
    	while(t --) {
    		solve();
    	}
    	return 0;
    }

[a5be7c6b602c4f88be59e35d4230ba23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/14/b3a86f8f24b14262a2bc9ef7e050fcc7.png