一直不会用 bitset，今天终于下定决心学一下。

bitset 是一个很好用的 STL，且时间复杂度和空间复杂度都很优秀。

bitset 是一个 01 串，每一位占一个 bit。

bitset 的下标是从右往左的。例如 $f_1=1$，那么得到的 bitset 应该是 00010 之类的东西。

所以后面的左移右移才是那样。

如何声明

首先，我们需要引用 <bitset> 头文件。

声明方式为

bitset<maxn> s;

maxn 为长度。

修改与运算

bitset 中每一个元素可以通过下标的方式访问。

进行单点修改时，直接访问位置然后赋值即可。

s[pos]=1;

bitset 还支持位运算，返回值为一个 bitset。

s<<=x;
s>>=x;
s&=s1;
s|=s1;
s^=s1;

复杂度

设计算机字长为 $\omega$，则一次操作的复杂度为 $O(\frac{n}{\omega})$。

因为 $\omega$ 位才占一个整形长度，所以空间复杂度为 $O(\frac{n}{\omega})$。

成员函数

reset

将 bitset 每一位都置为 0。

s.reset();

set

如果不传参数，会将每一位都置为 1。复杂度 $O(\frac{n}{\omega})$。

如果传参数，那么第一个参数为 $pos$，第二个参数为 $val$，意为把第 $pos$ 位置为 $val$。

如果不传 $val$，那么默认为 1。

s.set();
s.set(1);
s.set(1,0);

test

有一个参数 $pos$，返回第 $pos$ 位的值。

s.test(1);

any

若 bitset 内存在 1，则返回 1，否则返回 0。

cout<<s.any();

none

若 bitset 内所有位都是 0，则返回 1，否则返回 0。

cout<<s.none();

all

若 bitset 内所有位都是 1，则返回 1，否则返回 0。

cout<<s.all();

count

返回 bitset 内 1 的个数。

cout<<s.count();

flip

把每一位取反。

如果传参数 $pos$，那么就把第 $pos$ 位取反。

s.flip();
s.flip(1);

_Find_first

返回 bitset 第一个 1 的位置，不存在则返回 bitset 大小。

cout<<s._Find_first();

_Find_next

需要传参数 $pos$，返回下标严格大于 $pos$ 的位置中第一个 1 的位置。

cout<<s._Find_next(1);

应用

bitset 优化 dp

对于一些可行性 dp，可以 bitset 优化。

P1537 弹珠

这是一道多重背包，不过可以当 01 背包做。

但这是可行性背包，所以用 bitset 优化一下就可以了。

复杂度为 $O(\frac{n\sum w_i}{\omega})$

这里给出优化 01 背包的代码。

f[0]=1;
for(re int i=1;i<=n;++i) f|=(f<<w[i]);

Earn or Unlock *2200

首先可以发现，如果最后一共解锁了 $x$ 张牌，那么分数为 $(\sum_{i=1}^x a_i)-(x-1)$。

因为我们一开始只有一张牌，想解锁剩下的 $x-1$ 张就必须花 $x-1$ 的代价。

然后显然解锁的牌可以都拿，那么就是一个前缀和再减去代价。

所以我们只需要判断是否存在一种方案使得恰好解锁 $x$ 张牌即可。

复杂度 $O(n^2)$ 的 dp 显然，考虑优化。

但这是可行性 dp，可以用 bitset 优化。

事实上也是个 01 背包。

复杂度 $O(\frac {n^2}{\omega})$

一些细节：

1. $x$ 可以达到 $2n$。
2. 这里的背包比较特殊，因为如果我们用第 $i$ 张牌解锁后面的牌，那么恰好解锁 $i$ 张牌这个状态也就不能为后续提供转移了。所以我们还需要再开个数组，记录每种值能否被恰好取到。

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=2e5+10;
int n,ans;
int a[maxn],s[maxn];
bitset<maxn> f,g;
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(re int i=1;i<=n;++i) cin>>a[i],s[i]=s[i-1]+a[i];
    f[1]=1;
    for(re int i=1;i<=n;++i){
        f|=(f<<a[i]);
        g[i]=f[i];
        f[i]=0;
    }
    for(re int i=n+1;i<=(n<<1);++i) g[i]=f[i],s[i]=s[n];
    for(re int i=1;i<=(n<<1);++i) if(g[i]) ans=max(ans,s[i]-i+1);
    cout<<ans;
    return 0;
}

bitset 结合莫队

[Ynoi2017] 由乃的玉米田

区间询问可离线，考虑莫队。

我们维护两个 bitset，分别为 v1 和 v2。

设值域为 $V$。

如果 $x$ 在当前区间出现，那么 v1[x]=v2[V-x]=1。

对于减法操作，答案为 (v1&(v1<<x)).any()。

这很好理解。

假设 $a-b=x$，那么当前区间一定存在 $a$ 和 $a-x$。

所以我们把 v1 和 (v1<<x) 与一下，看看能否满足即可。

对于加法操作，答案为 (v1&(v2>>(V-x))).any()。

设 $b'=V-b$，那么 $b$ 在 v1 和 $b'$ 在 v2 中是对应的。

假设 $a+b=x$，那么 $a+V-b'=x$。

再移项一下，那么 $a-b'=x-V$。

这里已经转化成减法了。

因为 $x-V$ 是负数，所以把左移变成右移。

所以我们把 v1 和 (v2>>(V-x)) 与一下，看看能否满足即可。

对于乘法操作，我们可以考虑枚举约数，然后看 $i$ 和 $\frac {x}{i}$ 是否都存在。

这个复杂度是 $O(\sqrt n)$ 的。

对于除法操作，考虑根号分治。

对于 $x \ge \sqrt V$，直接暴力枚举，然后看 $i$ 和 $i\times x$ 是否都存在即可。

这个复杂度是 $O(\sqrt n)$ 的。

对于 $x < \sqrt V$，我们不使用莫队，而是单独处理。

首先将询问离线，然后枚举 $x$。

对于每个 $x$，我们扫一遍序列。

记 $last_i$ 表示 $i$ 当前最后一次出现的位置。

记 $ans_i$ 表示满足在 $[l,i]$ 中，同时存在 $a_i$ 和 $a_i \times x$ 或同时存在 $a_i$ 和 $\frac {a_i}{x}$ 的最靠右的 $l$ 的位置。

设当前扫到 $i$，那么先更新 $last_{a_i}$，再用 $last_{a_i\times x}$ 和 $last_{\frac {a_i}{x}}$ 更新 $res_i$ 即可。

扫完以后，我们回答以当前枚举到的 $x$ 作为 $x$ 的询问。

设询问区间为 $[l,r]$，那么只要 $l \le res_r$，该询问就合法。

因为 $x$ 只有 $\sqrt V$ 个，所以复杂度为 $O(n\sqrt n)$

综上，总复杂度为 $O(n\sqrt n)$。

code：

#include"bits/stdc++.h"
#define re register
#define int long long
using namespace std;
const int maxn=1e5+10,V=1e5,lim=300;
int n,m,Q,siz;
int a[maxn],buc[maxn],lst[maxn],res[maxn];
struct query{
    int op,l,r,x,id;
}q[maxn];
bitset<maxn> v1,v2,ans;
vector<query> q1[maxn];
inline bool cmp(query a,query b){return ((a.l/siz)^(b.l/siz))?(a.l/siz)<(b.l/siz):((a.l/siz)&1)?a.r<b.r:a.r>b.r;}
inline void add(int x){
    ++buc[x];
    v1[x]=v2[V-x]=(buc[x]);
}
inline void del(int x){
    --buc[x];
    v1[x]=v2[V-x]=(buc[x]);
}
inline void solve(){
    for(re int x=1,l;x<=lim;++x){
        memset(lst,0,sizeof lst);
        memset(res,0,sizeof res);
        l=0;
        for(re int i=1;i<=n;++i){
            lst[a[i]]=i;
            if(x*a[i]<=V) l=max(l,lst[x*a[i]]);
            if(a[i]%x==0) l=max(l,lst[a[i]/x]);
            res[i]=l;
        }
        for(auto v:q1[x]) ans[v.id]=(v.l<=res[v.r]);
    }
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
#endif
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>Q;
    for(re int i=1;i<=n;++i) cin>>a[i];
    for(re int i=1,op,l,r,x;i<=Q;++i){
        cin>>op>>l>>r>>x;
        if(op==4&&x<=lim) q1[x].push_back({op,l,r,x,i});
        else q[++m]={op,l,r,x,i};
    }
    solve();
    siz=sqrt(n)+1;
    sort(q+1,q+m+1,cmp);
    int l=1,r=0;
    for(re int i=1;i<=m;++i){
        while(r<q[i].r) add(a[++r]);
        while(l>q[i].l) add(a[--l]);
        while(r>q[i].r) del(a[r--]);
        while(l<q[i].l) del(a[l++]);
        if(q[i].op==1) ans[q[i].id]=(v1&(v1<<q[i].x)).any();
        if(q[i].op==2) ans[q[i].id]=(v1&(v2>>(V-q[i].x))).any();
        if(q[i].op==3) for(re int j=1;j*j<=q[i].x;++j) if(!(q[i].x%j)) if(v1[j]&&v1[q[i].x/j]) ans[q[i].id]=1;
        if(q[i].op==4) for(re int j=1;j*q[i].x<=V;++j) if(v1[j]&&v1[j*q[i].x]) ans[q[i].id]=1;
    }
    for(re int i=1;i<=Q;++i) cout<<(ans[i]?"yuno":"yumi")<<'\n';
    return 0;
}

参考文章：

扶苏的bitset浅谈