CFgym102354B Yet Another Convolution

发表于 分类于 ， ， 阅读次数：

2018-2019 Summer Petrozavodsk Camp, Oleksandr Kulkov Contest 2

题意：给出两个数组 ，求 ，，时限 。

由 ，只需正反做两遍 最后取 就好了。把 整体乘个 ，就变成好看的 一脸不可做……

考虑到经典 gcd 卷积暴力做复杂度很优，我们也尝试暴力。 考虑对每个 单独做。

问题变为：给定数组 和若干个 ，快速查询

这个 十分讨厌，考虑二分转化成判定性问题。多组询问就考虑整体二分。

如果，我们就能判定答案大于等于 。

对于求和我们就有很多办法了：

我们整体二分的时候，先把 离散化，然后按照如下流程分治:

  • 把 的位置都变成

  • 求和判定，把询问分到两个子区间里。

  • 继续分治。

这里我们需要一个数据结构，支持

  • 求 倍数处点权和
  • 单点修改

记 为 的倍数位置的和，暴力枚举约数修改。修改复杂度 ，查询。

注意到，在分治树上，每个询问都要历经 次判别；每个 都会产生 次修改。

注意到每次判别都需要 次查询,实际上,两部分复杂度同为 。

对于单个 的子问题，整体二分的总复杂度为

求解所有 的总复杂度为 且常数较小，轻松通过。