逃掉数学考试。感觉解几纯粹不给人希望。
这题还是比较有意思。做法是把每位分开预处当总共加了多少的时候这一位上是1的数字有多少个。然后每一层是线性的。询问是O(1)的。
然后发现自己的代码能力已经没救了。
#include <cstdio>
#include <cstring>
#define pow2(x) (1<<(x))
typedef long long dint;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
const int maxn = 100009;
const int maxl = 16;
const int maxv = pow2(maxl) - 1;
int n, m, c[maxv + 3], *t[maxl], b;
dint s;
void pre() {
for (int i = 0; i < maxl; ++ i) {
int len(pow2(i));
t[i] = new int[(len << 1) + 3];
t[i][0] = 0;
for (int j = 0; j <= maxv; ++ j)
if ((j >> i) & 1)
t[i][0] += c[j];
for (int j = 1; j <= len << 1; ++ j) {
t[i][j] = t[i][j - 1];
for (int k = (len << 1) - j; k <= maxv; k += len << 1)
t[i][j] -= c[k];
for (int k = (len >= j) ? (len - j) : ((len << 1) + len - j); k <= maxv; k += len << 1)
t[i][j] += c[k];
}
}
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
scanf("%d%d", &n, &m);
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; ++ i) {
int a;
scanf("%d", &a);
++ c[a & maxv];
}
pre();
s = b = 0;
while (m --) {
char opt[3];
int x;
scanf("%s%d", opt, &x);
if (opt[0] == 'A')
(b += x) &= maxv;
else
s += t[x][b & (pow2(x + 1) - 1)];
}
printf(lld "\n", s);
}