题目链接：uva 1406 - A Sequence of Numbers

题目大意；给定n个数，有两种操作：

• Q x：计算与2x取且不为0的数的个数
• C x：每个数加上x
  输出所有Q操作的和。

  解题思路：因为x最大为15，所以开16个树状数组，fenx[x]记录的是每个数取模2x+1的情况，然后有一个add值标记总共加了多少。根据add值确定原先数的范围。

  #include 
       
         #include 
        
          #include 
         
           using namespace std; #define lowbit(x) ((x)&(-x)) const int maxn = 1<<16; const int maxr = 16; int base[maxr+5], fenx[maxr+5][maxn+5]; int N, add; int query_treeArr (int* bit, int x) { int ret = 0; while (x) { ret += bit[x]; x -= lowbit(x); } return ret; } void insert_treeArr (int* bit, int x, int v) { while (x <= maxn) { bit[x] += v; x += lowbit(x); } } void init () { add = 0; for (int i = 0; i < maxr; i++) memset(fenx, 0, sizeof(fenx)); int x; for (int i = 0; i < N; i++) { scanf("%d", &x); for (int j = 1; j <= maxr; j++) { insert_treeArr(fenx[j-1], x % base[j] + 1, 1); } } } long long solve () { long long ret = 0; int x; char order[5]; while (scanf("%s", order) == 1 && strcmp(order, "E")) { scanf("%d", &x); if (order[0] == 'Q') { int have = add % base[x]; if (add & base[x]) { ret += query_treeArr(fenx[x], base[x] - have); ret += query_treeArr(fenx[x], base[x+1]) - query_treeArr(fenx[x], base[x+1] - have); } else ret += query_treeArr(fenx[x], base[x+1] - have) - query_treeArr(fenx[x], base[x] - have); } else add = (add + x) % base[16]; } return ret; } int main () { int cas = 1; base[0] = 1; for (int i = 1; i <= maxr; i++) base[i] = base[i-1] * 2; while (scanf("%d", &N) == 1 && N != -1) { init(); printf("Case %d: %lld\n", cas++, solve()); } return 0; }