简介
$bitset$ 确实是一个很好用的东西
分组 bitset
大概就是因为空间不够，所以连续 $B$ 个开一个 $bitset$
01背包
- 一般的背包的时间复杂度大概是 $O(\frac{nm}{w})$
- 如果 $n$ 个物体的体积和为 $O(n)$ 级别的数字，那么我们可以做到 $O(\frac{n\sqrt n}{w})$，具体做法：不同的体积只有 $O(\sqrt n)$ 种，对每种体积做二进制优化的多重背包，时间复杂度看似是 $O(\frac{n\sqrt n\log n}{w})$，但其实是 $O(\frac{n\sqrt n}{w})$
异或方程组
字符串匹配
设模板串长度为 $n$，匹配串长度为 $m$，那么使用 $bitset$ 可以做到 $O(\frac{nm}{w})$，做法就是对于模板串每个字符开一个 $bitset$ 存储该字符出现在哪个位置，然后枚举匹配串的每个位置，与对应的模板的 $bitset$ 与即可
1 | for (int i = 1; i <= n; ++i) B[ch(s[i])].set(i); |
例题
简要题意：给定一个长度为 $n$ 的字符串 $S$，现在有 $m$ 次操作，操作有两种，第一种操作是给定一个整数 $x$ 和一个字符 $ch$，将 $S_x$ 改成 $ch$；第二种操作给定 $[l,r]$ 和字符串 $T$，求字符串 $T$ 在 $S[l..r]$ 中出现了多少次
$|S|,m,\sum |T|\le 10^5$
简要题解：注意到数据范围全部是 $10^5$，我们直接考虑 $bitset$，第一个操作显然可以做到 $O(1)$，第二个操作我们直接做字符串匹配然后通过左移和右移把区间 $[l,r]$ 外的变成 $0$ 即可，时间复杂度 $O(\frac{n^2}{w})$
CF 914F Substrings in a String(bitset)
1
2bitset<N + 1> ans;
ans = ans >> x << N + x - y; // 将 [x,y] 外的区间都变成 0简要题意：给定一个长度为 $n$ 的字符串 $S$，现在有 $m$ 次询问，每次询问规定一个整数 $k_i$ 和一个字符串 $T_i$，对于每次询问要求找到一个字符串 $B$ 满足 $B$ 是 $S$ 的子串，且 $T_i$ 在 $B$ 中至少出现了 $k_i$ 次，保证每次询问的 $T_i$ 不同
$|S|,n,\sum |T|\le 10^5$
简要题解：首先我们有一个经典结论，对于一个长度为 $n$ 的字符串 $S$ 和 $m$ 个长度和为 $O(n)$ 的字符串 $T_i$，这 $m$ 个字符串在 $S$ 中出现的总次数为 $O(n\sqrt n)$
那么我们只需要能快速求出，每个字符串在 $S$ 中所有出现位置，然后暴力枚举每个出现位置即可，求出现位置可以使用 $bitset$，同时 $bitset$ 有一个函数可以实现 $O(\frac{n}{w}+c)$ 找出所有的 $1$ ，时间复杂度 $O(\frac{n^2}{w}+n\sqrt n)$
1
2bitset<N + 1> ans;
for (int p = ans._Find_first(); p <= N; p = ans._Find_next(p)) vec.push_back(p); // 找所有的 1
偏序
我们对于每个点开一个 $bitset$ 存储有多少点小于它，然后每一维小于它的数与起来即可
例题
三维偏序+分组 $bitset$，时间复杂度 $O(nB+\frac{n^2}{w})$，空间复杂度 $O(\frac{n^2}{wB})$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
using namespace std;
int n, m;
struct node {
int x[3], rk[3], id;
} a[maxn]; int I;
inline bool cmp(const node &u, const node &v) {
if (u.x[I] == v.x[I])
return make_tuple(u.x[0], u.x[1], u.x[2], u.id) <
make_tuple(v.x[0], v.x[1], v.x[2], v.id);
return u.x[I] < v.x[I];
}
const int N = 100000;
bitset<N + 1> B[3][sqtn];
int l[sqtn], r[sqtn], bl[maxn], blo, num, d[3][maxn];
void init_blo(int n) {
blo = min(n, 10); num = (n + blo - 1) / blo;
for (int i = 1; i <= n; ++i) bl[i] = (i - 1) / blo + 1;
for (int i = 1; i <= num; ++i) {
l[i] = (i - 1) * blo + 1;
r[i] = i * blo;
} r[num] = n;
for (int o = 0; o < 3; ++o) {
I = o; sort(a + 1, a + n + 1, cmp);
for (int i = 1; i <= n; ++i) a[i].rk[I] = i, d[o][i] = a[i].id;
for (int i = 1; i <= num; ++i) {
B[o][i] = B[o][i - 1];
for (int j = l[i]; j <= r[i]; ++j) B[o][i].set(a[j].id);
}
}
}
int ans[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
a[i].id = i;
for (int j = 0; j < 3; ++j) cin >> a[i].x[j];
} init_blo(n); sort(a + 1, a + n + 1, [](const node &u, const node &v) { return u.id < v.id; });
for (int i = 1; i <= n; ++i) {
bitset<N + 1> res, bits; res.set();
for (int o = 0; o < 3; ++o) {
int Bl = bl[a[i].rk[o]]; bits = B[o][Bl - 1];
for (int j = l[Bl]; j < a[i].rk[o]; ++j) bits.set(d[o][j]);
res &= bits;
} ans[i] = res.count();
} map<tuple<int, int, int>, int> mp;
for (int i = n; i; --i) {
tuple<int, int, int> t = make_tuple(a[i].x[0], a[i].x[1], a[i].x[2]);
if (mp.count(t)) ans[i] += mp[t];
++mp[t];
} vector<int> res(n);
for (int i = 1; i <= n; ++i) ++res[ans[i]];
for (int i = 0; i < n; ++i) cout << res[i] << "\n";
return 0;
}
有向图连通性
我们直接拿 $bitset$ 存储每个点可以到的点，然后在拓扑序逆序上维护这个东西即可，对于不是 $DAG$ 的图需要先缩点
一般的做法时间复杂度就是 $O(\frac{nm}{w})$，对于稠密图即 $m=O(n^2)$，我们可以将序列分块，不妨设块大小为 $B$，那么对于每个块，我们记录 $2^B$ 个子集的 $bitset$ 的并，然后块内我们 $B^2$ 暴力更新，块间我们求出每个点能到这个块内的多少点，这样本来需要做若干次 $bitset$ 交，但是因为我们预处理了 $2^B$ 个子集的答案，所以这里可以只做一次 $bitset$ 交
1 | void solve() { // g[u][v] 表示是否存在 u 到 v 的边, tp 表示拓扑序, f[u] 表示 u 可以到的点的 bitset |
例题
简要题意：给定 $n$ 个点 $m$ 条边的 $DAG$，求最多能删掉多少条边的同时不改变原图的连通性
$n\le 3\times 10^4,m\le 10^5$
简要题解：容易发现删边的操作没有后效性，所以我们能删就删，如果边 $(u,v)$ 可以被删掉，那么则意味着一定存在 $x$ 使得 $u$ 可以到达 $x$ 且 $x$ 可以到 $v$，这个东西可以直接用 $bitset$ 维护，时间复杂度 $O(\frac{nm}{w})$
简要题意：给定一个 $n$ 个点 $m$ 条边的 $DAG$，现在有 $q$ 次询问，每次询问给定 $u,v,l,r$，问从 $u$ 出发，只经过编号在 $[l,r]$ 内的边能否到达 $v$
$n,q\le 50000,m\le 100000$
简要题解：注意询问为 $DAG$ 可达性，显然只能使用 $bitset$，另外每个询问都固定了一个区间内的边，我们考虑离线
令 $S_i$ 表示有第 $i$ 条边的询问集合，同时我们令 $f_{u,i}$ 从 $u$ 出发，只经过 $[l_i,r_i]$ 内的边能否到达 $v_i$，这个东西我们拿 $bitset$ 优化，然后拓扑排序后，我们按照逆序更新 $f$ 即可，具体的，对于第 $k$ 条边 $(u,v)$，$f_u=f_u~or~(f_v~and~S_k)$，至于如何求 $S_k$，我们将询问离线后扫描线即可，但是由于空间限制，所以我们 $S_k$ 需要使用分组 $bitset$ 来存储
时间复杂度 $O(\frac{qm}{w}+Bm)$，空间复杂度 $O(\frac{nq}{Bw})$，$B$ 取 $5$ 即可满足空间限制