比如你要询问第k位为1的有多少个，那么其实就是询问如果只考虑后k位的话，在2^k~2^(k+1)-1之间的有多少个
那么维护16个树状数组，分别代表只考虑后i位的时候的情况
考虑整体加操作，记录一个全局标记ch维护当前整体加了多少，然后在插入和查询的时候都减去ch
这样的话查询区间有两个，一个是2^k-ch~2^(k+1)-1-ch，另一个是2^k+2^(k+1)-ch~2^(k+1)-1-ch
因为要考虑第k+1位是0还是1
还有负数不需要特判什么的……还是去看将狼踩尽的博客吧
#include<iostream> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<iomanip> #include<cstdlib> #include<cstdio> #include<map> #include<bitset> #include<set> #include<stack> #include<vector> #include<queue> using namespace std; #define MAXN 1010 #define MAXM 1010 #define ll long long #define eps 1e-8 #define MOD 1000000007 #define INF 1000000000 #define lb(x) x&-x int m; int N=1<<16; char o[MAXN]; int c[17][1000010]; int ch; map<int,int>h; void change(int *c,int x,int y){ for(;x<=N;x+=lb(x)){ c[x]+=y; } } int ask(int *c,int x){ int re=0; for(;x;x-=lb(x)){ re+=c[x]; } return re; } int main(){ int i; int x; scanf("%d",&m); while(m--){ scanf("%s",o); if(o[0]=='I'){ scanf("%d",&x); h[x-ch]++; for(i=1;i<=16;i++){ change(c[i],(x-ch&((1<<i)-1))+1,1); } } if(o[0]=='D'){ scanf("%d",&x); for(i=1;i<=16;i++){ change(c[i],(x-ch&((1<<i)-1))+1,-h[x-ch]); } h[x-ch]=0; } if(o[0]=='A'){ scanf("%d",&x); ch+=x; } if(o[0]=='Q'){ scanf("%d",&x); int ans=0; ans+=ask(c[x+1],min(max((1<<x+1)-(ch&((1<<x+1)-1)),0),1<<x+1)); ans-=ask(c[x+1],min(max((1<<x)-(ch&((1<<x+1)-1)),0),1<<x+1)); ans+=ask(c[x+1],min(max((1<<x+2)-(ch&((1<<x+1)-1)),0),1<<x+1)); ans-=ask(c[x+1],min(max((1<<x)+(1<<x+1)-(ch&((1<<x+1)-1)),0),1<<x+1)); printf("%d\n",ans); } } return 0; } /* 8 INS 1 QBIT 0 ADD 1 QBIT 0 QBIT 1 DEL 2 INS 1 QBIT 1 */
