题目描述

Steven 有一个 $N$ 个非负整数的数组。第 $i$ 个整数的（下标从 0 开始）是 $A_i$。

Steven 相当喜欢异或为偶数的 $A$ 的子区间。正式地说，$A$ 的一个子区间是一对下标 $(L, R)$，表示元素 $A_L, A_{L+1}, \dots, A_{R-1}, A_R$。这个子区间的异或和为 $A_L$ ^ $A_{L+1}$ ^ $\dots$ ^ $A_{R-1}$ ^ $A_R$。这里的 ^ 表示的是按位异或。

一个子区间是偶数异或的当它的异或和的二进制表示中有偶数个数为为 1。

Steven 想在这个数组上做 $Q$ 次修改。第 $i$ 次修改将 $P_i$ （下标从 0 开始）元素修改为 $V_i$。Steven 想知道，满足偶数异或的 $A$ 的子数组，在每次修改后最大是多少？

输入

第一行为 $T$ 表示有多少组测试数据。接下来为 $T$ 组测试数据。

每一个测试数据的第一行包含两个整数 $N$ 和 $Q$，分别表示 Steven 的数组中的数字个数和修改的次数。

第二行包含 $N$ 个整数。第 $i$ 个整数为 $A_i$，表示 Steven 数组中的第 $i$ 个整数。第 $i$ 次修改将 $P_i$ （下标从 0 开始）元素修改为 $V_i$。

然后接下来 $Q$ 行，表示修改。第 $i$ 行包含 $P_i$ 和 $V_i$，

输出

对于每个测试数据，输出一行包含 Case #x: y_1, y_2 ... y_Q，其中 $x$ 表示的是测试数据的编号（从 1 开始），$y_i$ 是最大的偶数异或子区间在第 $i$ 次修改后有多少元素。如果这样的子区间不存在，输出 0。

样例输入

2
4 3
10 21 3 7
1 13
0 32
2 22
5 1
14 1 15 20 26
4 26

样例输出

Case #1: 4 3 4
Case #2: 4

数据范围

• $1 \le T \le 100$.
• $0 \le A_i < 1024$.
• $0 \le P_i < N$.
• $0 \le V_i < 1024$.
• $1 \le N \le 10^5$.
• $1 \le Q \le 10^5$.

时间限制

• 一个测试数据有 40 秒。

原题链接

• X or What?

算法

(贪心) $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;
}