求找原题

学术版

ダ月 @ 2023-04-13 14:52:03

大致题意：序列 a_i，询问 m 次，每次给个 x 和 y 查询最小的 |i-j| 使得 a_i=x,a_j=y。

时间复杂度大概 O(m\sqrt{n}) 这个量级。算法是根号分治。

bdfs 无果，任何平台都行。

感谢。

by myee @ 2023-04-13 14:59:59

不强于第四分块吧。

做法一样的，就是第四分块多个单点修改。

by llingy @ 2023-04-13 15:00:16

@ダ月 P5397 的不带修版本

by myee @ 2023-04-13 15:01:37

哦不是单点修改，写错了。多一个颜色合并。

by ダ月 @ 2023-04-13 15:04:23

@llingy @myee thx

by myee @ 2023-04-13 15:05:15

不带修的情况，就是对 \ge T 的颜色和别的所有颜色的答案分别预处理一下，<T 的颜色之间的询问直接暴力归并计算，复杂度 O(n^2/T+qT)，取 T=n/\sqrt q 即为 O(n\sqrt q)。

by happybob @ 2023-04-13 18:31:09

第四分块

|