题解：P12525 [Aboi Round 1] 私は雨

· · 题解

这……这种问题，我当然知道，我……我可不是要说给你听的，我只是觉得你不知道的话太可怜了……对，就是这样……所以给我认认真真的记住！

考虑对 p 根号分治，>\sqrt V 的直接拿一个 vector 存一下，暴力二分就可以了。

对于 p<\sqrt V 的部分，序列分块预处理每一个块对 p 取模之后 =x 的答案，时间是 \mathcal O(n\sqrt{n\log n}) 询问也是二分即可。

注意我们可以加入一个剪枝：如果暴力枚举的 kp+x 的合法个数是在一个数以内的（我的代码里面是 500，经测试这是很合理的），那么久直接用 p>\sqrt V 的跑。

这里给出一点我的参数建议，可以稳过，不需要靠波动：

cin >> N >> opt;
L (i, 1, N) cin >> A[i], chmax(V, A[i]),
  pos[A[i]].push_back(i);
L (i, 1, V) sort (pos[i].begin(), pos[i].end());
const int B = sqrt(N) * 6.4;
L (i, 1, N) {
  bl[i] = (i - 1 + B) / B;
  if (!lpos[bl[i]]) lpos[bl[i]] = i;
  chmax (rpos[bl[i]], i);
}
const int VB = 100;
L (i, 1, N) {
  int blt = bl[i];
  L (v, 1, VB) g[blt][v][A[i] % v].push_back(A[i]);
}

跑的比大部分 \mathcal O(n\sqrt n) 题解快。