uva 1406 - A Sequence of Numbers(樹狀數組)

uva 1406 - A Sequence of Numbers(樹狀數組)

題目鏈接：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;
  }