bitset

具体描述

Substrings in a String

对于每一类字符建立一个$bitset$，记录它出现在原序列中的哪一个位置？

修改时暴力修改$bitset$内的元素，查询时暴力位移来压缩，注意为了保证合法，要压缩到结尾。

最后查询结尾即可，cout<<max(0,(int)((ans>>l+len-1).count()-(ans>>r).count()))<<endl;

注意$bitset.count()$是$unsigned int$类型。

Frequency of String

我们先用_Find_first() 与 _Find_next(x) 函数找到所有$m_i$的位置，

然后再暴力计算最小的包含连续$k$个$m_i$的子串的长度。

机器人游戏

再需要遍历数组的情况下，$bitset$ 计算信息的时间是数组$\frac{1}{32}$，

所以，我们用$bitset$维护$0,1,x,1-x$，用子集并f[x] = f[x & -x] | f[x ^ (x & -x)]就可以通过此题，

因为$bitset$可以快速计算数组操作，所以可以用位运算的技巧去维护或输出任意状态的值。

Alex and a TV Show

第三个操作比较麻烦，对值域内每个数预处理出其倍数中除以它不含平方因子的位置构成的 $bitset$，求答案的时候先按位与再 count() 就好了。

莫队结合bitset

$bitset$ 常用于常规数据结构难以维护的的判定、统计问题，而莫队可以维护常规数据结构难以维护的区间信息。把两者结合起来使用可以同时利用两者的优势。

具体描述

掉进兔子洞

一组询问的答案即所有区间的长度和减去三者的并集元素个数 $× 3$，莫队维护。

本题注意把当前元素离散化后的权值与当前区间的的出现次数之和作为往 $bitset$ 中插入的对象。

小清新人渣的本愿

用$bitset$维护每一个数字是否存在，加法 的话可以再维护一个$N-x$的$bitset$，其中 $N$ 为值域上限。

$3$操作直接枚举约数，查询两个乘数是否同时存在即可，莫队维护。

由乃的玉米田

多了个除法，分类讨论，$x >= \sqrt{n}$ 时暴力枚举除数，查询除数被除数是否同时存在，和乘法差不多，莫队维护。

对于 $x < \sqrt{n}$，我们可以预处理，枚举每一个 $x$，然后用双指针去维护每个$1<=i<=n$的离$i$最近且$<=i$的$tp_i$，满足$a_i$和$a_tp_i$的商为$x$，

然后询问时判断$l$是否$<=tp_r$即可。

WBLT

我们将$bitset$每$b$个分成一块，从左往右按位与起来。只要$bitset$不为空，则有这个长度的答案。

当$b$比较小时会被卡到$O(n^2)$，可以对于每一个 $b$ 分别处理。