laekov

逃掉数学考试。感觉解几纯粹不给人希望。

这题还是比较有意思。做法是把每位分开预处当总共加了多少的时候这一位上是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);

}