Google Kickstart 2019 Round D 题解

比赛题目

1. X or What?

Problem：
求动态数组的所有子区间的异或和中具有偶数个1的设置位的最长子区间的长度
Solution：
共N次查询Q次修改，小数据的数据范围为1 ≤ N ≤ 100，1 ≤ Q ≤ 100，大数据的数据范围为1 ≤ N ≤ 10^5，1 ≤ Q ≤ 10^5。首先暴力求每个子区间的异或和，然后计算异或和中1的位数，用 n &= (n -1) // 清除最低位的1。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 100005;
int a[N];
int BIT[N];
int n;

void update(int i, int val) {
    while (i <= n) {
        BIT[i] ^= val;
        i += i & -i;
    }
}

int preSum(int x) {
    int res = 0;
    while (x > 0) {
        res ^= BIT[x];
        x -= x & -x;
    }
    return res;
}

int xorSum(int i, int j) {
    return i == 1? preSum(j) : preSum(j)^preSum(i - 1);
}

bool checkEven(int val) {
    int num = 0;
    while (val)
    {
        val &= (val - 1);
        ++num;
    }
    return (num % 2 == 0);
}

int query() {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            int sum = xorSum(i, j);
            if (checkEven(sum)) {
                res = max(res, j - i + 1);
            }
        }
    }
    return res;
}

int main()
{
    int T;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    for (int t = 1; t <= T; t++) {
        int q;
        cin >> n >> q;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            update(i, a[i]);
        }
        vector<int> ress;
        for (int i = 0; i < q; i++) {
            int idx, val;
            cin >> idx >> val;
            idx++;
            update(idx, (a[idx]^val));
            a[idx] = val;
            ress.push_back(query());
        }
        cout << "Case #" << t << ": ";
        for (int i = 0; i < q; i++) {
            cout << ress[i] << " ";
        }
        cout << endl;
    }
}

针对小数据维护区间的异或前缀和 S0 = 0, S1 = A1 and Si = Si - 1 xor Ai