C++ STL bitset总结

基础用法

余下的就是例题了

[BZOJ3687]简单题

考虑\(DP\)，设\(f[i][j]\)表示前\(i\)个元素的算数和为\(j\)的子集个数，有：

\[f[i][j]=f[i-1][j]+f[i-1][j-a[i]]
\]

时间复杂度为\(O(n\sum a_i)\)，显然会超时。

考虑到题目要求计算的是异或和，所以我们实际上只需维护前\(i\)个元素的算数和为\(j\)的子集个数的奇偶性，这个可以使用bitset实现。bitset第\(j\)位为\(1\)代表前\(i\)个元素的算数和为\(j\)的子集个数为奇数，转移时：

\[Bitset=Bitset\ or\ (Bitset<<a[i])
\]

即可。

由于并行运算（我也不知道这是什么东西），时间复杂度为\(O(n\frac{\sum a_i}{32})\)（并且常数好像还很小），只要我们有信仰，就一定可以\(AC\)。

建议做此题之前先翻阅一下BZOJ的讨论区，数据有锅，害的ErkkiErkko怒送\(1TLE+2WA\)。

蒟蒻代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <bitset>

#define rin(i,a,b) for(int i=(a);i<=(b);i++)

#define rec(i,a,b) for(int i=(a);i>=(b);i--)

#define trav(i,x) for(int i=head[(x)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

const int MAXN=1005;

const int MAXNUM=2000005;

int n,a[MAXN];

std::bitset<MAXNUM> bs;

int main(){

	n=read();

	bs[0]=1;

	int x;

	rin(i,1,n){

		x=read();

		bs^=(bs<<x);

	}

	int ans=0;

	rin(i,0,2000000) if(bs[i])

		ans^=i;

	printf("%d\n",ans);

	return 0;

}

Shift-And&Shift-Or字符串匹配算法

Wikipedia

神犇博客

蒟蒻代码

std::bitset<MAXN> now,sta[30];

Shift-And

rin(i,1,m) sta[t[i]-'a'].set(i-1);

rin(i,1,n){

	now=((now<<1).set(0)&sta[s[i]-'a']);

	if(now[m-1]) printf("%d\n",i-m+1);

}

Shift-Or

now.set();

memset(sta,0xff,sizeof sta);

rin(i,1,m) sta[t[i]-'a'].reset(i-1);

rin(i,1,n){

	now=((now<<1)|sta[s[i]-'a']);

	if(!now[m-1]) printf("%d\n",i-m+1);

}

练手题：[BZOJ4503]两个串

这不是FFT模板题吗？

对啊。

虽然这个算法跑得比FFT慢（多了）。

通配符怎么解决啊？

通配呗。

[BZOJ4939][Ynoi2016]掉进兔子洞

这一道题和下一道题大概是我学习bitset的出发点。

一开始想了半天用权值线段树怎么做，然而越想越不可做，套上莫队也不行。于是去百度题解，仿佛打开了通往新世界的大门。

题解告诉我们如果用bitset上的一段连续的位表示对应的一个数出现过几次，于是就可以先用莫队求出三个区间的的权值bitset，然后对这三个的权值bitset做与运算，答案即为\(\sum len-ResultBitset.count()\)。

要特别提到的是，为了节省空间我们需要分批处理询问。

时间复杂度\(O(n \sqrt{n}+\frac{n^2}{32})\)。（不知道这算不算\(O(n^2)\)过\(1e5\)）

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <bitset>

#define rin(i,a,b) for(int i=(a);i<=(b);i++)

#define rec(i,a,b) for(int i=(a);i>=(b);i--)

#define trav(i,x) for(int i=head[(x)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

const int MAXN=100005;

const int SIZE=340;

const int T=25000;

int n,m,a[MAXN],b[MAXN];

int cnt,ans[T+5],has[MAXN];

std::bitset<MAXN> bs[T+5],now;

struct Qu{

	int l,r,lk,id;

	inline friend bool operator < (Qu x,Qu y){

		if(x.lk!=y.lk) return x.lk<y.lk;

		if(x.lk&1) return x.r<y.r;

		return x.r>y.r;

	}

}q[T*3+5];

inline void mo(){

	memset(has,0,sizeof has);

	memset(bs,0xff,sizeof bs);

	std::sort(q+1,q+cnt+1);

	int nowl=1,nowr=0;

	now.reset();

	rin(i,1,cnt){

		while(nowl>q[i].l){

			nowl--;

			now.set(a[nowl]+has[a[nowl]]);

			has[a[nowl]]++;

		}

		while(nowr<q[i].r){

			nowr++;

			now.set(a[nowr]+has[a[nowr]]);

			has[a[nowr]]++;

		}

		while(nowl<q[i].l){

			has[a[nowl]]--;

			now.reset(a[nowl]+has[a[nowl]]);

			nowl++;

		}

		while(nowr>q[i].r){

			has[a[nowr]]--;

			now.reset(a[nowr]+has[a[nowr]]);

			nowr--;

		}

		bs[q[i].id]&=now;

	}

	cnt/=3;

	rin(i,1,cnt){

		printf("%d\n",ans[i]-bs[i].count()*3);

	}

}

int main(){

	n=read(),m=read();

	rin(i,1,n){

		a[i]=b[i]=read();

	}

	std::sort(b+1,b+n+1);

	rin(i,1,n){

		a[i]=std::lower_bound(b+1,b+n+1,a[i])-b;

	}

	rin(i,1,m){

		q[++cnt].l=read();

		q[cnt].lk=(q[cnt].l-1)/SIZE+1;

		q[cnt].r=read();

		q[cnt].id=(i-1)%T+1;

		ans[(i-1)%T+1]+=q[cnt].r-q[cnt].l+1;

		q[++cnt].l=read();

		q[cnt].lk=(q[cnt].l-1)/SIZE+1;

		q[cnt].r=read();

		q[cnt].id=(i-1)%T+1;

		ans[(i-1)%T+1]+=q[cnt].r-q[cnt].l+1;

		q[++cnt].l=read();

		q[cnt].lk=(q[cnt].l-1)/SIZE+1;

		q[cnt].r=read();

		q[cnt].id=(i-1)%T+1;

		ans[(i-1)%T+1]+=q[cnt].r-q[cnt].l+1;

		if(cnt==T*3){

			mo();

			cnt=0;

			memset(ans,0,sizeof ans);

		}

	}

	if(cnt) mo();

	return 0;

}

[BZOJ4810][Ynoi2017]由乃的玉米田

话说bitset的骚操作还真多，感觉很难一下子全部掌握。

这道题可以稍微地类比一下生成函数。

莫队求出每个区间的权值bitset。考虑询问，减的话直接右移后做与，加的话再维护一个翻转的权值bitset就好了（有种\(FFT\)画风），乘的话，枚举给定乘积的约数再在bitset里查询即可。

时间复杂度\(O(n \sqrt{n}+\frac{n^2}{32})\)。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <bitset>

#define rin(i,a,b) for(int i=(a);i<=(b);i++)

#define rec(i,a,b) for(int i=(a);i>=(b);i--)

#define trav(i,a) for(int i=head[(a)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

inline int read(){

	int x=0;char ch=getchar();

	while(ch<'0'||ch>'9') ch=getchar();

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x;

}

const int MAXN=100005;

const int SIZE=340;

int n,m,a[MAXN],cnt[MAXN];

bool ans[MAXN];

std::bitset<MAXN> f,g;

struct Qu{

	int opt,l,r,x,lk,id;

	inline friend bool operator < (Qu x,Qu y){

		if(x.lk!=y.lk) return x.lk<y.lk;

		if(x.lk&1) return x.r<y.r;

		return x.r>y.r;

	}

}q[MAXN];

int main(){

	n=read(),m=read();

	rin(i,1,n){

		a[i]=read();

	}

	rin(i,1,m){

		q[i].opt=read();

		q[i].l=read();

		q[i].r=read();

		q[i].x=read();

		q[i].lk=(q[i].l-1)/SIZE+1;

		q[i].id=i;

	}

	std::sort(q+1,q+n+1);

	int l=1,r=0;

	rin(i,1,m){

		while(l>q[i].l){

			l--;

			cnt[a[l]]++;

			f.set(a[l]);

			g.set(MAXN-5-a[l]);

		}

		while(r<q[i].r){

			r++;

			cnt[a[r]]++;

			f.set(a[r]);

			g.set(MAXN-5-a[r]);

		}

		while(l<q[i].l){

			cnt[a[l]]--;

			if(!cnt[a[l]]){

				f.reset(a[l]);

				g.reset(MAXN-5-a[l]);

			}

			l++;

		}

		while(r>q[i].r){

			cnt[a[r]]--;

			if(!cnt[a[r]]){

				f.reset(a[r]);

				g.reset(MAXN-5-a[r]);

			}

			r--;

		}

		if(q[i].opt==1){

			if((f&(f>>q[i].x)).any()) ans[q[i].id]=1;

		}

		else if(q[i].opt==2){

			if((f&(g>>(MAXN-5-q[i].x))).any()) ans[q[i].id]=1;

		}

		else{

			int lim=sqrt(q[i].x);

			rin(j,1,lim){

				if(q[i].x%j) continue;

				if(f[j]&&f[q[i].x/j]){

					ans[q[i].id]=1;

					break;

				}

			}

		}

	}

	rin(i,1,m){

		if(ans[i]) printf("yuno\n");

		else printf("yumi\n");

	}

	return 0;

}

Extra. 三维偏序

这是一个在洛谷的三维偏序模版题会MLE的算法。

把三维分开处理，每次只对其中的一维排序。这样对于每个点很容易算出在这一维不大于这个点的所有点的集合，用bitset存储，最后三个集合求交就好了。

但是我们需要开\(1e5\)个\(1e5\)的bitset，而题目的空间限制是\(512MB\)，大概只能开\(4e9\)位，于是就愉快地MLE了。

Update on 2018/12/7：好吧，这里为了卡空间要套个分块，但是在洛咕上会TLE，极限数据\(2.5s+\)。感谢UOJ群的各位和yyb，放个yyb博客的链接在这：链接，yyb orz。

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <cctype>

#include <algorithm>

#include <bitset>

#define rin(i,a,b) for(register int i=(a);i<=(b);i++)

#define rec(i,a,b) for(register int i=(a);i>=(b);i--)

#define trav(i,x) for(register int i=head[(x)];i;i=e[i].nxt)

using std::cin;

using std::cout;

using std::endl;

typedef long long LL;

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}

	return x*f;

}

const int MAXN=100005;

const int SIZE=335;

const int BLOCK=(MAXN>>5)+5;

int n,k,dat[3][MAXN],blg[MAXN],rez[MAXN];

int Table[65536];

inline void init(){

	rin(i,0,65535) Table[i]=Table[i>>1]+(i&1);

}

inline int query(unsigned int x){

	return Table[x>>16]+Table[x&65535];

}

struct Bitset{

	unsigned int Element[BLOCK],siz;

	Bitset(){

		siz=0;

	}

	inline friend void operator &= (Bitset &x,Bitset y){

		x.siz=0;

		rin(i,0,BLOCK-1) x.Element[i]&=y.Element[i],x.siz+=query(x.Element[i]);

	}

	inline void set(){

		siz=n;

		memset(Element,0xff,sizeof Element);

	}

	inline void set(int x){

		int nth=(x>>5),pos=x-(nth<<5);

		Element[nth]|=(1u<<pos);

		siz++;

	}

};

Bitset now,ret,bs[3][MAXN/SIZE+5];

struct Pair{

	int x,id;

	inline friend bool operator < (Pair x,Pair y){

		return x.x<y.x;

	}

}a[3][MAXN];

inline int L(int x){

	return (x-1)*SIZE+1;

}

inline int R(int x){

	return x*SIZE;

}

inline int find(int d,int x){

	int l=1,r=n,retint;

	while(l<=r){

		int mid=((l+r)>>1);

		if(a[d][mid].x<=x) retint=mid,l=mid+1;

		else r=mid-1;

	}

	return retint;

}

inline void getset(int d,int x){

	int pos=find(d,x);

	ret=bs[d][blg[pos]-1];

	rin(i,L(blg[pos]),pos) ret.set(a[d][i].id);

}

int main(){

	n=read(),k=read();

	init();

	rin(i,1,n){

		a[0][i]=(Pair){dat[0][i]=read(),i};

		a[1][i]=(Pair){dat[1][i]=read(),i};

		a[2][i]=(Pair){dat[2][i]=read(),i};

		blg[i]=(i-1)/SIZE+1;

	}

	rin(d,0,2){

		std::sort(a[d]+1,a[d]+n+1);

		rin(i,1,blg[n]){

			bs[d][i]=bs[d][i-1];

			rin(j,L(i),R(i)) bs[d][i].set(a[d][j].id);

		}

	}

	rin(i,1,n){

		now.set();

		rin(d,0,2) now&=(getset(d,dat[d][i]),ret);

		rez[now.siz-1]++;

	}

	rin(i,0,n-1) printf("%d\n",rez[i]);

	return 0;

}

巴特西