题解：P9212 「蓬莱人形」
lovely_qiqi
·
·
题解
首先转换题目给出的不等式。
在 x<y 时，容易发现要么不等式左右两边都取模，要么都不取模，可以得到 a_i 取模 m 后的范围是 [0,m-y-1] \lor [m-x,m-1]。x>y 时为 [m-x,m-y-1]，x=y 时无解。以上可以通过小学数学得到。
对于区间 [l,r] 显然可以转换成 [0,r] - [0,l-1]，问题转换成了求 a_i \bmod m < x 的个数，其中 (m,x) 多组询问。
直接做并不好做，但是一个 trick 是对于取模和除法问题可以使用根号分治，因为在被除数 L 一定时，商和余数一定有一个 \le\sqrt{L}。
对于小于阈值 B 的模数，我们考虑余数，直接暴力地用 a_{i,j} 表示 x \bmod i=j 中 x 的个数，然后统计和查询的复杂度是 O(nB+qB)的。
对于大于阈值的模数，我们考虑商，商的种类数是只有 \frac{V}{B} 的，对于每一种 c 只需要找到 a_i-cm <x 且在 \frac{a_i}{m}=c 范围内的 a_i 个数就行了，在值域上做查询的次数为 \frac{qV}{B} 的，而一开始修改的次数为 n 。这个东西用常规的数据结构做的话查询显然带一只 \log 或者更高，于是总复杂度变成了 O(\frac{qV\log q}{B}+qB)，平衡一下 B 取 \sqrt{qlogq} ，显然在第一部分爆炸了。
于是需要考虑一种查询 O(1) 而修改最高 O(\sqrt{V}) 的做法，如果用分块的话只需要维护一个整块前缀和散块内前缀和。于是这个题就做完了，总时间复杂度在 O(qB+nB+\frac{qV}{B}+n\sqrt{V}) 在 B=\sqrt{V} 时取得理论最小，为 O(q\sqrt{V}+n\sqrt{V})。