1.bitset优化空间

考虑 DAG上的可达性 ，给定一个 $n$ 个节点和 $m$ 条边的 DAG，包含 $q$ 次查询，其中查询的形式为 "顶点 $v$ 是否可由顶点 $u$ 到达" ，其中 $1\leq n,m,q \leq 10^5$ 且不允许有类似 $\Omicron(n^2)$ 的空间复杂度，其中包括开 $n$ 个长度为 $n$ 的 bitset

一个比较经典的解法是让 $\text{dp[v]} $ 成为一个 bitset ，当 $v$ 可以到达 $u$ 时令 $\text{dp[v][u] = 1}$ 。这个方法在大多数情况是可行的，但是 $10^5$ 个长度为 $10^5$ 的 bitset 也会占用大量内存，因此我们可以用 $64$ 位整数来代替 bitset ，并重复该算法 $\frac{n}{64}$ 次。在第 $k$ 次执行该算法时，我们令 $\text{dp[v]}$ 成为一个 $64$ 位整型用来储存 $64k, \; 64k + 1 \; ... \; 64k + 63$ 是否可以到达 $v$ 。

2.避免在莫队中出现 log

考虑如下问题：给定一个长度为 $n$ 的序列和 $n$ 次询问，询问区间 mex ，不强制在线。

线段树固然可行，但我们现在要考虑莫队。

在利用莫队维护 mex 的时候，我们同时也需要一个 set<int> 来维护在该区间所有未出现的整数，这样在每次指针后我们都可以用 $\Omicron(\log n)$ 的复杂度来维护答案，这样莫队总的复杂度就做到了 $\Omicron(n^{\frac{3}{2}}\log n)$ ，但是这样太慢了！

显然复杂度的瓶颈是 set<int> ，我们之所以用它是为了支持以下操作：

插入一个元素，当前单次复杂度 $\Omicron(\log n)$ ，需要操作 $\Omicron(n^{\frac{3}{2}})$ 次
删除一个元素，当前单次复杂度 $\Omicron(\log n)$ ，需要操作 $\Omicron(n^{\frac{3}{2}})$ 次
查询最小值，当前单次复杂度 $\Omicron(\log n)$ ，需要操作 $\Omicron(n) $ 次

我们注意到前两种操作更频繁一点，但他们的时间复杂度相同，因此我们可以牺牲最后一个操作的复杂度，使得前两种操作更高效。

我们需要这样一个数据结构：

$\Omicron(1)$ 插入元素
$\Omicron(1)$ 删除元素
$\Omicron(n^{\frac{1}{2}})$ 查询最小值

因此我们可以将值域分块，插入删除显然可以 $\Omicron(1)$ 完成，同时我们维护是否每个块中的元素已经全部出现，自小到大找到一个非满的块暴力查询即可。

这是在莫队中至关重要的一件事，确保指针能在 $\Omicron(1)$ 复杂度下移动，即使有时需要牺牲查询的复杂度

3.根号优化背包/ “3k trick”

假设有 $n$ 个物品，每个物品都有一个非负数权值 $a_i$ ，且 $\sum a_i = m$ ，询问是否能从中选出一些物品使得其权值和为 $w$ 。

我们假设有三个相同权值的物品 $a,a,a$ 。注意到用 $a,2a$ 可以替换掉这三个物品，我们可以重复这个过程直到每个权值至多有两件物品，且有 $\sum a_i = m$ ，因此至多只有 $\Omicron{(m ^ {\frac{1}{2}})}$ 个物品。因此我们可以直接进行背包，同时物品的数目减少至 $\Omicron{(m^{\frac{1}{2}})}$ 个，这在大部分情况下是更好的复杂度

这个技巧大多出现在序列 $a$ 能被某些特殊形式划分的时候，例如他们可能代表一个图的分量，请看示例：

问题链接

$\text{给定一个含有 n 个字母的字母表以及一个含有 m 个单词的字典}$

$\text{你想用两种颜色给字母染色，使得每个单词中相邻字母都是不同颜色的，并尽量减少两种颜色字母的数量差} $

我们考虑把整个过程看成二分图，最初的输入会产生一定的分量，我们可以考虑翻转其中的一部分使得两边大小尽量相同。最初我们可以翻转全部的分量，使得左边的分量变小。然后我们可以每次选择翻转一部分分量，使得左侧部分大小增加 $a_i$ ，且 $ \sum a_i $ 为定值。这样就可以利用上述技巧解决掉整个问题了。