bitset是什么
bitset是一个神奇的库，经常可以在你觉得过不了的时候帮你优化掉一个64或者32的常数，帮你成功卡过去
定义：bitset < 10 > s
但是要注意，bitset中下标和我们理解的数字顺序是相反的，例如当你把s用一个字符串赋值的时候:
string st = "100100";
bitset < 10 > s(st);
下标和st中是反的，即s[0] = ‘0‘, s[1] = ‘0‘, s[2] = ‘1‘，以此类推，cout << s 的时候也是按照反下标的顺序输出的。
当你进行s << 1的操作的时候，是把每个数字的下标+1了，相当于把这个二进制数字左移一位（因为要反着看嘛）
这些操作的复杂度都是 \(O(N/w)\) （N是bitset的位数，w是机器字长）
有了这些东西就可以做题啦
bitsest优化DP
因为不是DP手所以决定瞎讲(bushi
当DP方程出现 \(dp(i, j) |= dp(i - 1, j - x)\)的时候，其实是一个一维的01数组向高位移动x位再或上原数据，那么我们就可以把这个01数组设位s，每次操作变成s = s | (s << x);
这个转移的复杂度是 \(O(N / w)\) 的。
Luogu 3674 小清新人渣的本愿
这道题才是重点
首先离线的话很容易想到莫队，但是这个的转移完全不是 \(O(1)\) 的，不同询问之间转换异常困难。
于是可以用 bitset 来做，首先要明确一点，bitset 优化的并不是转移的过程，转移必须是 \(O(1)\) 的，不然时间就不够用了，所以转移部分的时间复杂度是 \(O(n^{3/2})\)，bitset 优化的是每次得出答案的过程，即得到答案这一部分的复杂度是 \(O({n*m}/w)\)，两部分加起来，复杂度可以接受。
那么具体怎么做呢
- 对于减法，这种是最简单的，维护一个值域大小的 bitset，每一位表示数字 i 有没有在 [L， R] 的区间内，这个转移显然是 \(O(1)\) 的，然后在莫队中每次把区间挪完，开始计算答案的时候，可以发现答案就是
s & (s<<x)的1的个数，因为两个数字如果差为 x，则一个数字加上x之后就等于另一个数字，这样计算不会重复也不会遗漏。 - 对于加法，同样维护一个值域大小的 bitset，因为a + b = x相当于a = -b + x，所以第 i 位表示数字 -i + N有没有出现过（+N是为了让值为正），之后再用
s & (s >> (N - x))来把它变成-b+x。 - 对于乘法，直接 \(O(√N)\) 枚举因数就行了。
代码如下：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int unit, a[N], cnt[N];
struct node {
int opt, l, r, num, id;
bool operator < (const node &x) const {
return l / unit == x.l / unit
? (r == x.r ? 0 : ((l / unit) & 1) ^ (r < x.r)) : l < x.l;
}
} Ask[N];
bitset < N > s, s2;
inline void Del(int x) {
cnt[a[x]]--;
if (!cnt[a[x]]) s[a[x]] = 0, s2[N - a[x]] = 0;
}
inline void Add(int x) {
cnt[a[x]]++; s[a[x]] = 1, s2[N - a[x]] = 1;
}
bool ans[N];
int main() {
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
unit = sqrt(m);
for (int i = 1; i <= m; i++)
scanf("%d%d%d%d", &Ask[i].opt, &Ask[i].l, &Ask[i].r, &Ask[i].num), Ask[i].id = i;
sort(Ask + 1, Ask + m + 1);
int L = 1, R = 0;
for (int i = 1; i <= m; i++) {
while (L > Ask[i].l) Add(--L);
while (R < Ask[i].r) Add(++R);
while (L < Ask[i].l) Del(L++);
while (R > Ask[i].r) Del(R--);
if (Ask[i].opt == 1)
ans[Ask[i].id] = (s & (s << Ask[i].num)).any();
else if (Ask[i].opt == 2)
ans[Ask[i].id] = (s & (s2 >> (N - Ask[i].num))).any();
else {
bool flag = false;
for (int j = 1; j * j <= Ask[i].num; j++)
if (Ask[i].num % j == 0)
if (s[j] && s[Ask[i].num / j])
flag = true;
ans[Ask[i].id] = flag;
}
}
for (int i = 1; i <= n; i++)
ans[i] ? puts("hana") : puts("bi");
return 0;
}