樹狀數組 + 位運算 LA 4013 A Sequence of Numbers

?

題目傳送門

題意：n個數，兩種操作，一是每個數字加x，二是查詢& (1 << T) == 1 的個數

分析：因為累加是永遠的，所以可以離線處理。樹狀數組點是c[16][M] 表示數字x%(1 << j) 后的數字pos，考慮第j位的個數。當詢問時根據add不同的值不同的處理情況。

#include <bits/stdc++.h>
using namespace std;typedef long long ll;
const int N = 1e5 + 5;
const int R = (int) 1 << 16;
const int M = R + 10;
struct BIT  {int c[16][M];void init(void) {memset (c, 0, sizeof (c));}void updata(int b, int pos) {pos++;  //pos 可能等于0while (pos < M)   {c[b][pos] += 1;pos += pos & -pos;}}int sum(int b, int pos) {pos++;int ret = 0;while (pos > 0) {ret += c[b][pos];pos -= pos & -pos;}return ret;}
}bit;int main(void)  {int n, cas = 0;while (scanf ("%d", &n) == 1)   {if (n == -1)    break;bit.init ();for (int x, i=0; i<n; ++i) {scanf ("%d", &x);for (int j=0; j<16; ++j)    {bit.updata (j, x % (1 << (j + 1)));}}ll add = 0, ans = 0; char str[2];while (scanf ("%s", &str) == 1) {if (str[0] == 'E')  break;if (str[0] == 'C')  {       //離線int x;  scanf ("%d", &x);add += x;if (add >= R)   add %= R;}else    {int t;  scanf ("%d", &t);int tail = add % (1 << t);if (add & (1 << t))    {        //(1<<t)位上已經有1ans += bit.sum (t, (1 << t) - 1 - tail);        //+tail 之前之后，都是0ans += bit.sum (t, (1 << (t + 1)) - 1) - bit.sum (t, (1 << (t + 1)) - 1 - tail);    //+tail 之前1，之后0}else    {ans += bit.sum (t, (1 << (t + 1)) - 1 - tail) - bit.sum (t, (1 << t) - 1 - tail);   //+tail 之后1}}}printf ("Case %d: %lld\n", ++cas, ans);}return 0;
}

　　

?