题解：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

的跑。

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

CPP

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)

题解快。

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

文章操作

相关推荐

评论

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