推荐博客：扶苏的bitset浅谈
笔记：
-
定义时可以赋值 bitset<10> b(8);bitset<1005> b(string("01010101"))
会分别存储为0000001000、0001010101
-
函数 b.to_ulong() 和 b.to_ullong() 会把b里面的数转化为一个 unsighed long int/unsigned long long（32位/64位)（int和long int实际上都是32位）。
注意当b中的数字大于转化过去的最大值时，会RE（不是b定义的位数，而是b中的数字）
-
bitset的下标是[0,n)，cout输出时顺序为 n-1 n-2 n-3……3 2 1 0。
-
常用函数：b.reset(); b.set(); b.test(); b.any(); b.none(); b.count(); b.flip();
分别表示：全变成0；全变成1；第i位是否为1；是否有1；是否全0；1的个数；翻转
例题：
洛谷 P1537 弹珠
物品总数很少，所以可以多重背包转化为01背包。状态转移方程为:
用bitset可以将其优化，b的第i位表示能否组成价值和为i，则转移方程为：
然而实际上跑得很慢，我也不知道为啥。。
洛谷 P3674 小清新人渣的本愿
莫队+bitset优化。
开一个bitset c，第i位表示数字i有无出现。
开一个bitset d，第i位表示数字N-d是否出现。
-
若判断有无 a-b=x，可以转化成 a=b+x，即判断 c&(c<<x) 是否有1，即 c&(c<<x).any()；
-
若判断有无 a+b=x，可以转化成 a-(n-b)=x-n，再转化成 (n-b)=a+(n-x)，即判断 d&(c<<(n-x)).any();
-
若判断有无 a*b=x，可以暴力 \(O(\sqrt x)\) 枚举 x 的因数，\(O(1)\) 查询即可。
然后用莫队将询问离线操作，保证左端点和右端点最多移动 \(n\sqrt n\) 次，而每次移动更新bitset都是 \(O(1)\) 的。
最后总的时间复杂度为 \(O(n\sqrt n + m(\frac{c}{w} + \sqrt c))\)
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<bitset>
using namespace std;
template<class T>inline void read(T &x)
{
x=0;register char c=getchar();register bool f=0;
while(!isdigit(c))f^=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
if(f)x=-x;
}
const int maxn=1e5+5;
int n,m,a[maxn],in[maxn],vis[maxn],sq;
bitset<maxn+5> c,d;
struct node{
int op,l,r,x,id,ans;
}q[maxn];
bool cmp1(node a,node b){
if(in[a.l]!=in[b.l]) return in[a.l]<in[b.l];
if(in[a.l]&1) return a.r<b.r;
return a.r>b.r;
}
bool cmp2(node a,node b){
return a.id<b.id;
}
void insert(int x){
x=a[x];
if(vis[x]==0) c.set(x),d.set(maxn-x);
vis[x]++;
}
void del(int x){
x=a[x];
if(vis[x]==1) c.reset(x),d.reset(maxn-x);
vis[x]--;
}
int main(){
ios::sync_with_stdio(false);
read(n);read(m);
sq=sqrt(n);
if(sq*sq<n) sq++;
int cnt=1,cnt_now=0;
for(int i=1;i<=n;i++){
cnt_now++;
if(cnt_now==sq){
cnt++;
cnt_now=0;
}
in[i]=cnt;
}
for(int i=1;i<=n;i++) read(a[i]);
for(int i=1;i<=m;i++){
read(q[i].op);read(q[i].l);read(q[i].r);read(q[i].x);q[i].id=i;
}
sort(q+1,q+m+1,cmp1);
int l=1,r=0;
for(int i=1;i<=m;i++){
while(r<q[i].r) insert(++r);
while(r>q[i].r) del(r--);
while(l>q[i].l) insert(--l);
while(l<q[i].l) del(l++);
if(q[i].op==1) q[i].ans=(c&(c<<q[i].x)).any();
else if(q[i].op==2) q[i].ans=(d&(c<<(maxn-q[i].x))).any();
else {
int sq=sqrt(q[i].x);
for(int j=1;j<=sq;j++){
if(q[i].x%j==0){
if(c.test(j)&&c.test(q[i].x/j)){
q[i].ans=1;
break;
}
}
}
}
}
sort(q+1,q+m+1,cmp2);
for(int i=1;i<=m;i++){
if(q[i].ans) puts("hana");
else puts("bi");
}
return 0;
}