莫队算法

莫队算法

有一个序列,且有一些区间询问,便可以考虑用神奇的莫队算法!

实现

莫队是一种离线算法,用到了分块的思想,将序列分块,设每个块的长度为 S 。在输入所有询问之后,按 (\lfloor\frac{l}{S}\rfloor,r) 二元组从小到大排序,之后按顺序暴力移动左右端点并统计答案。

时间复杂度

设序列的长度为 n ,询问个数为 m ,从 [l,r] 扩展到 [l - 1, r], [l + 1, r], [l, r - 1], [l, r + 1] 的时间复杂度为 O(f(n)) ,于是从 (l1, r1) 转移到 (l2, r2) 的时间为 O((|l1 - l2| + |r1 - r2|) * f(n)) 对于每一个块中的所有询问,最多使 r 移动 n ,每个询问最多使 l 移动 S ,一共有 \frac{n}{S} ,相邻两个块转移的时间复杂度为 O(n * f(n)) ,所以总时间复杂度为 O((\frac{n ^ 2}{S}+mS+\frac{n ^ 2}{S}) * f(n)) ,当 n, m 同阶时,使 S = \sqrt{n} ,总时间复杂度即为 O(n\sqrt{n} * f(n))

模板

 

莫队算法
Tagged on:     

One thought on “莫队算法

  • 2017年12月7日 at 下午12:13
    Permalink

    %%%
    膜拜FKC大佬

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注