洛谷 P5355
这个题是在 洛谷 P3674 的基础上增加了商为 \(x\) 的查询，其他的操作可以看 我的博客。
设 \(\dfrac{b}{a} = x\)，考虑根号分治，取 \(B = \sqrt V\)。
- 当 \(x \ge B\) 时，\(a \le B\)。暴力枚举 \(a\)，查询时序列中是否有 \(ax\) 即可。
- 当 \(x < B\) 时，可以枚举 \(x\) 单独做，从小到大枚举 \(r\) 时，维护最大的满足条件的 \(l\)（设 \(pos_i\) 表示 \(i\) 上一次出现的位置，用 \(pos_{a_r \cdot x}, pos_{a_r / x}\) 更新），查询一下即可。
加减法都是 \(O(\frac{n}{\omega})\)，乘除法 \(O(\sqrt V)\)。