bitset 的用法

bitset 是一個存 0/1 的大小不可變的容器，它的空間效率和時間效率極其快，快 32 倍，所以會被用于一些暴力優(yōu)化成正解。

個人的理解，這個東西把一大堆壓到了一塊，相當于一個小分塊，所以才變快了，手寫一個也就是把一個 ull 當作 64 個位置存。

記一下這個玩意的用法吧。

聲明

聲明也就很簡單。

bitset <MN> s;

別忘了這個是固定大小的。

訪問，修改

支持下標訪問

s[0]=1;
cout<<s[114514]<<'\n';

這個東西也支持各種各樣的位運算。

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

這基本上就夠用了。

一些函數(shù)

這邊僅僅寫一些自認為有用的。

重置用 reset, 全都便成 0。

s.reset();

大規(guī)模設(shè)置用set, 第一個參數(shù)是 pos， 第二個參數(shù)是 val;

如果什么都不傳默認把所有的位置都設(shè)為 1, 時間復(fù)雜度 \(O(\frac{n}{w})\)

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

any 如果存在1就返回 true;

cout<<s.any();

none 如果都是 0 返回 true。

cout<<s.none();

all 如果全部都是 1 則返回 true。

cout<<s.all();

count 返回 1 的個數(shù)

cout<<s.count();

flip 對每一位取反，如果加上 pos 就是這一位。

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

_Find_first 會返回第一個 1 的位置，不存在返回大小。

cout<<s._Find_first();

_Find_next 返回位置嚴格大于 pos 的第一個 1 的位置。

cout<<s._Find_next(1);