526互联

CF797E Array Queries

发布时间 2023-09-21 23:39:04作者: 御坂夏铃

这种位置弄来弄去的题一般就分两种，倍增预处理或者根号分治。

现在步长种类很多，只能考虑后者，对步长 \(k\) 进行根号分治：

  • \(k>\sqrt n\)，直接暴力，最多跳 \(O(\sqrt n)\) 次。
  • \(k<\sqrt n\)，最多有 \(O(\sqrt n)\) 种 \(k\)，预处理它们只需要 \(O(n\sqrt n)\) 的空间和时间。