关于此题的简易做法
Taystered
·
·
题解
本人左边是出题人，右边是想出方法的 dalao，由中间的蒟蒻代笔。
对于每一个询问，可以轻易的想到将 [l,r] 的答案拆开来求，即求 ans(1∼r)-ans(1∼(l-1))，问题转化为求 ans 函数。
显而易见的是 ans(x)=\sum_{i=1}^{n}\lfloor\dfrac{x-a_i}{k}\rfloor，假设 \sum_{i=1}^{n}(x-a_i)=pk+q，则 ans(x)=p。
与此同时 q=\sum_{i=1}^{n}(x-a_i)\;\text{mod}\;k，可以 O(n) 进行预处理，然后就有：
p=\dfrac{\sum_{i=1}^{n}(x-a_i)-\sum_{i=1}^{n}(x-a_i)\;\text{mod}\;k}{k}
同时要考虑计算 ans(x) 时 x \leq a_i 的情况，就可以用 O(1) 的优秀时间复杂度算出答案了。
总时间复杂度：O(n)。希望口胡没有锅。
我现在就找出题人加强数据......这题顶多普及。