[Ynoi2017] 由乃的玉米田

题意

给定一个序列，回答四种询问，判断一个数是否能够由一个区间中两个数进行加减乘除中的一种运算得到，无解输出 \(-1\) 。

题解

首先使用莫队。

加减操作使用莫队与两个 bitset 简单维护， 复杂度为 \(\dfrac{nm}{w}\)。

乘操作考虑暴力分解质因数然后查询两数是否出现过同样维护。

除操作考虑根号分治，大于则暴力莫队找。

小于则单独处理，暴力处理出对于每一个 \(x\) 离每一个位置最近的一个位置使得合法然后放回去看区间是否满足。

\(O(\dfrac{nm}{w} + n( \sqrt{n}+ \sqrt{m})\)