X or What?
符号约定：
- $\xor$ 表示异或。
- popcount($x$) 表示非负整数 $x$ 的二进制表示里数字 1 出现的次数。例如，$13 = 1101_2$，则 popcount(13) = 4。
注意到，popcount($a \xor b$) = popcount($a$) + popcount($b$) - 2 * number of positions both $a$ and $b$ are set。
因此，popcount($a \xor b$) 的奇偶性 = (popcount($a$) + popcount($b$)) 的奇偶性。
区间 $[L, R]$ 的异或和的 popcount 为偶数 $\iff$ $L - 1, R$ 这两个前缀的异或和的 popcount 同奇偶。
分别考虑异或和的 popcount 为奇数的前缀、异或和的 popcount 为偶数的前缀。
改变 $A_p$ 对答案的影响：
若 $A_p$ 的 popcount 的奇偶性不变，则答案亦不变，否则 $p, p+1, \dots, n - 1$ 这些前缀的异或和的 popcount 的奇偶性翻转。
解法 1
用线段树维护前缀的异或和的 popcount 的奇偶性。
支持查询：
- 异或和的 popcount 为偶数的前缀最后一次出现的位置。
- 异或和的 popcount 为奇数的前缀第一次/最后一次出现的位置。
bool bit_even(int x) {
return (__builtin_popcount(x) & 1) == 0;
}
struct node {
int n[2];
int flipped;
void flip() {
swap(n[0], n[1]);
flipped ^= 1;
}
};
const int N = 100005;
node seg[4 * N];
int sum[N];
void push_up(int i) {
int l = i * 2, r = l + 1;
for (int j = 0; j < 2; j++) {
seg[i].n[j] = seg[l].n[j] + seg[r].n[j];
}
}
void build (int i, int l, int r) {
seg[i].flipped = 0;
if (l == r) {
seg[i].n[0] = bit_even(sum[l]);
seg[i].n[1] = 1 - seg[i].n[0];
return;
}
int mid = (l + r) / 2;
build(i * 2, l, mid);
build(i * 2 + 1, mid + 1, r);
push_up(i);
}
void push_down(int i) {
if (seg[i].flipped) {
int l = i * 2, r = i * 2 + 1;
seg[l].flip();
seg[r].flip();
seg[i].flipped = 0;
}
}
int find_first(int v, int i, int l, int r) {
if (seg[i].n[v] == 0) return r + 1;
if (l == r) return l;
push_down(i);
int mid = (l + r) / 2;
int res = find_first(v, i * 2, l, mid);
if (res <= mid) {
return res;
}
return find_first(v, i * 2 + 1, mid + 1, r);
}
int find_last(int v, int i, int l, int r) {
if (seg[i].n[v] == 0) return l - 1;
if (l == r) return l;
push_down(i);
int mid = (l + r) / 2;
int res = find_last(v, i * 2 + 1, mid + 1, r);
if (res > mid) {
return res;
}
return find_last(v, i * 2, l, mid);
}
void flip(int i, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return;
if (ql <= l && r <= qr) {
seg[i].flip();
return;
}
int mid = (l + r) / 2;
push_down(i);
flip(i * 2, l, mid, ql, qr);
flip(i * 2 + 1, mid + 1, r, ql, qr);
push_up(i);
}
int main() {
#ifdef LOCAL
ifstream in("main.in");
cin.rdbuf(in.rdbuf());
#endif
int T; cin >> T;
for (int cas = 1; cas <= T; ++cas) {
cout << "Case #" << cas << ":";
int n, q; cin >> n >> q;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum[i] = sum[i - 1] ^ a[i];
}
build(1, 1, n);
while (q--) {
int p, v;
cin >> p >> v;
++p;
if (bit_even(v) != bit_even(a[p])) {
flip(1, 1, n, p, n);
}
a[p] = v;
cout << " " << max(find_last(0, 1, 1, n), find_last(1, 1, 1, n) - find_first(1, 1, 1, n));
}
cout << endl;
}
return 0;
}