首页 > 代码库 > [BZOJ2568]比特集合

[BZOJ2568]比特集合

2024-07-16 11:17:50   227人阅读

这道题的思路还是比较好想的喵~

首先令数组 C[k][num] 表示 2 进制最后 k 位 <=num 的数的个数

查询第 k 位为 1 即询问 C[k][(1<<k+1)-1]-C[k][(1<<k)-1] 的值

因为要支持插入、删除，C 数组应使用树状数组或线段树来维护

然后可以用类似于标记永久化的方法，把 ADD 操作搞掉喵~

 

但是细节部分处理起来就比较麻烦了，WA 了好多次莫名其妙的 A 了

我也不敢写太多……

 

 1 #include <cstdio> 2 #include <map> 3  4 namespace IOspace 5 { 6     inline char getch() 7     { 8         register char ch; 9         do ch=getchar(); while (ch!=‘A‘ && ch!=‘I‘ && ch!=‘D‘ && ch!=‘Q‘);10         return ch;11     }12     inline int getint()13     {14         register int num=0;15         register char ch;16         do ch=getchar(); while (ch<‘0‘ || ch>‘9‘);17         do num=num*10+ch-‘0‘, ch=getchar(); while (ch>=‘0‘ && ch<=‘9‘);18         return num;19     }20     inline void putint(int num, char ch=‘\n‘)21     {22         char stack[15];23         register int top=0;24         if (num==0) stack[top=1]=‘0‘;25         for ( ;num;num/=10) stack[++top]=num%10+‘0‘;26         for ( ;top;top--) putchar(stack[top]);27         if (ch) putchar(ch);28     }29 }30 31 int N;32 int add;33 std::map<int, int> s;34 int sum[17][65537];35 inline int lim(int x) {return (1<<x+1)-1;}36 inline int min(int x, int y) {return x<y?x:y;}37 inline int max(int x, int y) {return x>y?x:y;}38 inline int lowbit(int x) {return x & -x;}39 inline void update(int, int, int);40 inline int query(int, int);41 42 int main()43 {44     N=IOspace::getint();45     for ( ;N;N--)46     {47         char ch=IOspace::getch(); int x=IOspace::getint();48         if (ch==‘A‘) add+=x;49         if (ch==‘I‘)50         {51             x-=add;52             s[x]++;53             for (int i=0;i<16;i++) update(i, (x & lim(i))+1, 1);54         }55         if (ch==‘D‘)56         {57             x-=add;58             int t=s[x];59             s[x]=0;60             for (int i=0;i<16;i++) update(i, (x & lim(i))+1, -t);61         }62         if (ch==‘Q‘)63         {64             int l=1<<x, r=lim(x);65             int ans=0;66             ans+=query(x, min(max(r-(add & lim(x))+1, 0), 1<<16));67             ans-=query(x, min(max(l-(add & lim(x)), 0), 1<<16));68             l+=1<<x+1, r+=1<<x+1;69             ans+=query(x, min(max(r-(add & lim(x))+1, 0), 1<<16));70             ans-=query(x, min(max(l-(add & lim(x)), 0), 1<<16));71             IOspace::putint(ans);72         }73     }74 75     return 0;76 }77 inline void update(int k, int i, int v)78 {79     for ( ;i<=1<<16;i+=lowbit(i)) sum[k][i]+=v;80 }81 inline int query(int k, int i)82 {83     int ret=0;84     for ( ;i;i-=lowbit(i)) ret+=sum[k][i];85     return ret;86 }
本傻也不知道自己在写什么的系列1

 


联系
我们