算法

(贪心,二进制,异或) $O(T \cdot (N + Q) \cdot \log N \cdot \log A_i)$

1. 我们观察子区间为偶数异或区间的性质。我们不妨将每个数字换成二进制表示，如果一个子区间为偶数异或区间，则该子区间所有数字二进制表示中的 1 一共有偶数个。
2. 原因是因为异或的性质，在相同位置上的 1 经过偶数次就会变成 0，而经过奇数次才会留下一个 1。我们可以在每个位上最多只保留一个 1，不影响总数 1 的奇偶性。所以，如果一共有偶数个 1，无论这些 1 的位在哪里，最后留下的 1 一定是偶数个。
3. 到这里这道题就很简单了，如果整个区间有偶数个 1，答案为 $N$。否则，我们找到区间中最左边第一个不是偶数个 1 的位置 $l$，和区间中最右侧第一个不是偶数个 1 的位置 $r$，$[l + 1, n - 1]$ 和 $[0, r - 1]$ 就是合法区间，二者取长度最大即可。
4. 维护区间最左边和最右边第一个奇数个 1 的位置可以用 C++ 的 set，我们首先将所以奇数个 1 的位置放入有序集合，如果集合的个数为偶数，则直接输出 $N$；否则，取出集合的两个端点。维护时，将集合中那个位置删除（如果原数字有奇数个 1），然后再将那个位置插入（如果新的数字有奇数个 1）。

时间复杂度

• 初始化时，需要遍历整个数字，判断每个数字的 1 的个数，并将奇数个 1 的位置放入集合中，这一步的复杂度为 $O(N \cdot \log N \cdot \log A_i)$。
• 对于每个询问，可能需要增删查集合，所以每个询问的复杂度为 $O(\log N \cdot \log A_i)$。
• 故总时间复杂度为 $O(T \cdot (N + Q) \cdot \log N \cdot \log A_i)$。

空间复杂度

• 每个测试数据，我们仅需要一个有序集合来维护，所以空间复杂度为 $O(N)$。

C++ 代码

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;


const int N = 100010;
int T, n, q;
int a[N];
int main() {
    scanf("%d", &T);
    for (int test = 1; test <= T; test++) {
        set<int> ones;
        scanf("%d%d", &n, &q);
        for (int i = 0; i < n; i++) {
            scanf("%d", &a[i]);
            int t = 0;
            for (int j = 0; j < 10; j++) {
                if ((a[i] >> j) & 1) {
                    t++;
                }
            }
            a[i] = t & 1;
            if (t & 1) {
                ones.insert(i);
            }
        }
        printf("Case #%d:", test);
        while (q--) {
            int x, y;
            scanf("%d%d", &x, &y);
            int t = 0;
            for (int j = 0; j < 10; j++) {
                if ((y >> j) & 1) {
                    t++;
                }
            }
            if (a[x] & 1) {
                ones.erase(x);
            }
            a[x] = t & 1;

            if (a[x] & 1) {
                ones.insert(x);
            }

            if (ones.size() & 1) {
                int l = *ones.begin();
                int r = *ones.rbegin();
                printf(" %d", max(r, n - l - 1));
            } else {
                printf(" %d", n);
            }
        }
        printf("\n");
    }
    return 0;
}