stl大法好之bitset

今天考试的时候有一道用bitset的题目… litble不会bitset… 按照以往的惯例，学习一个stl就是要打一段测试代码：

#include<bits/stdc++.h> using namespace std; #define RI register int int main() { bitset<10> a(string("0011010"));//建立一个大小为10的bitset cout<<a<<endl;//0000011010 bitset<10> b(string("100100110")); cout<<b<<endl;//0100100110 cout<<(a&b)<<endl;//0000000010 cout<<(a|b)<<endl;//0100111110 cout<<(a^b)<<endl;//0100111100 cout<<(a<<1)<<endl;//0000110100 cout<<(a>>1)<<endl;//0000001101 cout<<(a.size())<<endl;//返回bitset的位数:10 cout<<(a.count())<<endl;//返回1的个数:3 cout<<(a.any())<<endl;//返回是否有1:1 cout<<(a.none())<<endl;//返回是否无1:0 a.set();cout<<a<<endl;//全部变成1:1111111111 a.reset();cout<<a<<endl;//全部变成0:0000000000 a.set(3);cout<<a<<endl;//将第3位（从0开始计算）变成1:0000001000 a.reset(3);cout<<a<<endl;//将第3为变成0:0000000000 b.flip();cout<<b<<endl;//将b全部取反：1011011001 b.flip(2);cout<<b<<endl;//将第2位取反:1011011101 b[9]=0;cout<<b<<endl;//访问第9位:0011011101 unsigned int orz=b.to_ulong();//将bitset转化成usigned int cout<<orz<<endl;//221 return 0; }

使用bitset的时空复杂度大约是$O(\frac{n}{32})$的，因为它的基本原理是每32个连续的数字压成一个int。 当然如果你觉得bitset常数太大，可以试试某Cai佬的方法：手写bitset，还可以用long long压 按照以往的惯例，学一个stl就要用这个stl水一道题… 选择洛谷P3674 莫队，并维护两个bitset，一个叫orz存数x是否存在，一个叫cai存数N-x（N是一个大数）是否存在。 然后对于第一个询问，就是看是否存在a-b=x即a=x+b。所以直接查(orz&(orz<<x)).any()即可。 第二个询问，看是否存在a+b=x即N-b+x-N=a，查(orz&(cai>>(BIG-x))).any()。 第三个询问，枚举较小的约数。

#include<bits/stdc++.h> using namespace std; int read() { int q=0;char ch=' '; while(ch<'0'||ch>'9') ch=getchar(); while(ch>='0'&&ch<='9') q=q*10+ch-'0',ch=getchar(); return q; } #define RI register int const int N=100005,BIG=100000; int n,m,sqn; int a[N],pos[N],js[N],ans[N]; bitset<N> orz,cai; struct node{int op,l,r,x,id;}q[N]; bool cmp(node a,node b) {return pos[a.l]==pos[b.l]?a.r<b.r:a.l<b.l;} void add(RI x,RI num) { if(js[x]==0&&num==1) orz[x]=1,cai[BIG-x]=1; if(js[x]==1&&num==-1) orz[x]=0,cai[BIG-x]=0; js[x]+=num; } int query1(RI x) {return (orz&(orz<<x)).any();} int query2(RI x) {return (orz&(cai>>(BIG-x))).any();} int query3(RI x) { for(RI i=1;i*i<=x;++i) if(x%i==0&&orz[i]&&orz[x/i]) return 1; return 0; } int main() { n=read(),m=read(),sqn=sqrt(n); for(RI i=1;i<=n;++i) a[i]=read(),pos[i]=(i-1)/sqn+1; for(RI i=1;i<=m;++i) q[i]=(node){read(),read(),read(),read(),i}; sort(q+1,q+1+m,cmp); RI he=1,ta=0; for(RI i=1;i<=m;++i) { while(ta<q[i].r) ++ta,add(a[ta],1); while(ta>q[i].r) add(a[ta],-1),--ta; while(he<q[i].l) add(a[he],-1),++he; while(he>q[i].l) --he,add(a[he],1); if(q[i].op==1) ans[q[i].id]=query1(q[i].x); else if(q[i].op==2) ans[q[i].id]=query2(q[i].x); else ans[q[i].id]=query3(q[i].x); } for(RI i=1;i<=m;++i) puts(ans[i]?"hana":"bi"); return 0; }