20260225 测试 笔记

退役三月，脑子已经退化，看着身边的人一个个退竞，我也不远了。

A

$n\le 100,q\le {10}^5,b\le 5\times {10}^4$。

• 注意不到 $f_i=f_i\vee f_{i-k}$（$i\in [k,n]$，$k$ 是常量）的 $0/1$ 背包转移方程式可以使用 Bitset 进行 $O(\frac{n}{\omega })$ 时间的转移。

• 注意不到完全背包是一种特殊的多重背包，多重背包是一种特殊的 $0/1$ 背包。

• 注意不到如果插入一个小的数，那这个集合几乎马上每个数都能被表示出来，后面的更新可以跳过很多；如果插入一个大的数，那么完全达不到更新 $\log b$ 次，由于 $n$ 很小，复杂度比较玄学。

时间复杂度 $O(q\log b\times b÷\omega )$，空间复杂度 $O(nb)$。

B

$N,Q\le 2\times {10}^5$。

https://www.luogu.com.cn/problem/P3295，同类题目。

不同之处在于在线和离线，注意到在线每次都要下传一堆标记。

• 注意不到每一层只会被并查集合并 $O(N)$ 次，如果下传到已经合并了的地方直接退出，那么总体下传标记的复杂度就是 $O(N\log N\alpha (N))$ 而不是 $O(QN\alpha (N))$。

时间复杂度 $O(N\log N\alpha (N)+Q)$，空间复杂度 $O(N\log N)$。