关于莫队复杂度

ppip @ 2022-07-27 19:02:20

by UnyieldingTrilobite @ 2022-07-27 19:05:09

因为是默认了 n,m 同阶，所以复杂度分析得比较粗略

by irris @ 2022-07-27 19:05:53

@ppip oiwiki 就有吧

by Yahbim @ 2022-07-27 19:08:46

@ppip

1. 你这分析不是 O(n\sqrt n+m\sqrt n) 的么

by ppip @ 2022-07-27 19:11:29

@Yahbim

1. 只讨论左端点
2. 感谢帮助

by ppip @ 2022-07-27 19:12:00

@AlgorithmerSnow

1. 没看懂
2. 感谢帮助

by panyanppyy @ 2022-07-27 19:14:24

https://oi-wiki.org/misc/mo-algo/#_5

by panyanppyy @ 2022-07-27 19:14:31

@ppip

by ducati @ 2022-07-27 20:18:43

我不会告诉你这是从我的某篇博客里原模原样贴过来的。

Analysis

为方便叙述，令排序后的二元组序列为 (l_1,r_1)(l_2,r_2),\cdots,(l_m,r_m)，且 \forall i \in [1,m] 有 1 \le l_i,r_i \le n。

首先分析第一维度。根据 Method，第一维度 l 所在的块必定是递增的；也就是说，l_i<l_{i-1} 的必要条件是 l_i,l_{i-1} 在同一块中。这样一来，最劣情况即为 l_1,l_2,\cdots,l_m 在同一块内反复横跳。因此，总共跳动的距离为 O(mB) 级别。

接着分析第二维度。根据 Method，在第一维度 l 所在块一定时，第二维度 r 必定是递增的；也就是说，r_i<r_{i-1} 的必要条件是 l_i,l_{i-1} 在不同块中。而 l_i,l_{i-1} 异块的情况至多只会出现 O(\frac n B) 次，所以这一部分跳动的总距离便是 O(\frac {n^2} {B})。此外，r_i>r_{i-1} 的贡献相当于在 \frac {n} {B} 轮中扫描一遍序列的复杂度，也是 O(\frac {n^2} {B})。从而，第二维度上总共跳动的距离为 O(\frac {n^2} {B})。

综上所述，二维莫队（又称普通莫队）的时间复杂度是 O(\frac {n^2} {B}+mB)。

Summary

观察这个复杂度 O(\frac {n^2} {B}+mB)，可以发现：

• 当取 B=\sqrt n 时，时间复杂度为 O((n+m)\sqrt n)。
• 当取 B=\frac {n} {\sqrt m} 时，时间复杂度为 O(n \sqrt m)。

至于选择哪个好，就要看具体题目啦。

by ducati @ 2022-07-27 20:20:31

@ppip 感觉大概写得没错（？）

by ppip @ 2022-07-27 20:27:16

@ducati 您是怎么找到我帖子的（感动）

感谢orz