洛谷 P3674

洛谷 P3674

对于第 \(3\) 类操作，直接 \(O(\sqrt n)\) 枚举因数，判断即可。

对于减法操作，使用一个 bitset \(b\)，维护有哪些数在区间内。设 \(p - q = x\)，那么 \(p = q + x\)。所以只需要 b & (b << x) 中有 1 即可。对于加法操作，维护一个倒过来的 bitset 即可。

至于如何维护 \(b\)，使用莫队即可。

时间复杂度：\(O(\frac{n^2}{w} + n\sqrt n)\)