Chips on a Board
题目就是让我们求\((x - l)\)的异或和，对于减\(l\)，我们不好处理，考虑在减\(l\)的限制下拆位，那么我们发现对于在\([l + 2^j, l + 2 ^ {j+1} - 1]\)的数最高位在减\(l\)后都为\(1\)且为第\(j\)位。
这启示我们对于每一个\(l\)维护\([l,l+2^j-1]\)数在减\(l\)下的异或和，显然
其中\(S_i\)表示\([1,i]\)中有多少个数。
在处理一组询问\(l,r\)时，从最高位开始考虑，如果这一位\(k\)可能有数，那么将\([l,l+2^k-1]\)的异或值用\(f\)算出，对于第\(k\)位，那么只跟\([l+2^k,r]\)中数个数的奇偶性有关，接着只需考虑\([l+2^k,r]\)中数以后位的异或值，时间复杂度\(O(\log m)\)。
Code
#include<cstdio>
#include<iostream>
#define IN inline
using namespace std;
const int N = 2e5 + 5;
int n, m, s[N], f[N][22], Q; char ch[N];
IN int read() {
int t = 0,res = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) t |= (ch == '-');
for (; isdigit(ch); ch = getchar()) res = (res << 3) + (res << 1) + (ch ^ 48);
return t ? -res : res;
}
int main() {
n = read(), m = read();
for (int i = 1, q; i <= n; i++) q = read(), s[q]++;
for (int i = 1; i <= m; i++) s[i] += s[i - 1];
for (int j = 1; j <= 20; j++)
for (int i = 1; i <= m - (1 << j) + 1; i++)
f[i][j] = f[i][j - 1] ^ f[i + (1 << j - 1)][j - 1] ^
((s[i + (1 << j) - 1] - s[i + (1 << j - 1) - 1]) & 1 ? (1 << j - 1) : 0);
Q = read();
for (int i = 0; i < Q; i++) {
int l = read(), r = read(), ans = 0;
for (int j = 20; j >= 0; j--)
if (l + (1 << j) <= r + 1) {
ans ^= f[l][j] ^ ((s[r] - s[l + (1 << j) - 1]) & 1 ? (1 << j) : 0);
l += (1 << j);
}
if (ans == 0) ch[i] = 'B'; else ch[i] = 'A';
}
printf("%s\n", ch);
}