传送门
思路
经典的 bitset
优化莫队
先考虑减法:由 \(a-b=x\) 可得 \(a=b+x\),那么我们用 bitset
记录对应的数字是否出现过,然后在询问时,我们将 bitset
整体向左移 \(x\) 位,再与原 bitset
取交集,如果不为 \(0\),显然是可行的
然后加法与减法类似:考虑 \(a=Mx-a'\),那么有 \(a-b'=a+b-Mx=x-Mx\),移项后 \(a+Mx-x=b'\),那我们就再用一个 bitset
维护 \(Mx-a\),询问时与减法相同
乘法我们直接暴力枚举 \(\sqrt x\) 个因子进行判断即可,复杂度与莫队的复杂度是同阶的
除法倒是有些棘手,我们考虑用根号分治:
-
若 \(x\ge \sqrt {Mx}\)(\(Mx\) 是最大的数),那么我们直接像乘法那样暴力枚举就行了
-
若 \(x< \sqrt{Mx}\),我们考虑不使用莫队;我们对每种询问 \(x\) 进行一次扫描线:\(la[num]\) 记录 \(num\) 目前出现最靠右的位置,\(Rpos[i]\) 记录扫到 \(i\) 时,满足存在两个数商为 \(x\)(没有余数)的最右左端点;流程如下:当扫到 \(i\) 时,将 \(la[a[i]]=i\),\(Rpos[i]=max(la[a[i]*x], la[a[i]/x],Rpos[i-1])\);处理询问时,我们只需要比较 \(ql\)(询问区间的左端点)是否小于等于 \(Rpos[qr]\) 即可
代码
#include
#include
#include
#include
#include
#include
#include
#include