1. 普通莫队算法

这里只讲到了普通莫队算法(不带修改),内容有诸多是借鉴与网上的(O(∩_∩)O 谢谢啦!),主要借鉴了:https://blog.sengxian.com/algorithms/mo-s-algorithm 和 ZYF(或 JYF)神犇的博客(懒得帮你搞超链接了)。

概述

莫队算法是由莫涛提出的算法,可以解决一类离线区间询问问题,适用性极为广泛。同时将其加以扩展,便能轻松处理树上路径询问以及支持修改操作。

形式

对于序列上的区间询问问题,如果从 $[l,r]$的答案能够 $O(1)$扩展到 $[l-1,r],[l+1,r],[l,r+1],[l,r-1]$(即与 $[l,r]$相邻的区间)的答案,那么可以在 $O(n√n)$的复杂度内求出所有询问的答案。

实现

离线后排序,顺序处理每个询问,暴力从上一个区间的答案转移到下一个区间答案(一步一步移动即可)。

排序方法

对于区间 $[l,r]$, 以 l 所在块的编号为第一关键字,r 为第二关键字从小到大排序。

模板
int l = 0, r = 0, nowAns = 0;

inline void move(int pos, int sign) {
    // update nowAns
}

void solve() {
    BLOCK_SIZE = int(ceil(pow(n, 0.5)));
      sort(querys, querys + m);
    for (int i = 0; i < m; ++i) {
        const query &q = querys[i];
        while (l > q.l) move(--l, 1);
        while (r < q.r) move(r++, 1);
        while (l < q.l) move(l++, -1);
        while (r > q.r) move(--r, -1);
        ans[q.id] = nowAns;
    }
}
复杂度分析

以下的情况在 $n$ 和 $m$ 同阶的前提下讨论。

首先是分块这一步,这一步的时间复杂度毫无疑问地是 $O(\sqrt{n}\cdot\sqrt{n}\log\sqrt{n}+n\log n)=O(n\log n)$ ;

接着就到了莫队算法的精髓了,下面我们用通俗易懂的初中方法来证明它的时间复杂度是 $O(n\sqrt{n})$ ;

证:令每一块中 $L$ 的最大值为 $\max_1,\max_2,\max_3, \cdots , \max_{\lceil\sqrt{n}\rceil}$ 。

由第一次排序可知, $\max_1 \le \max_2 \le \cdots \le \max_{\lceil\sqrt{n}\rceil}$ 。

显然,对于每一块暴力求出第一个询问的时间复杂度为 $O(n)$ 。

考虑最坏的情况,在每一块中, $R$ 的最大值均为 $n$ ,每次修改操作均要将 $L$ 由 $\max_{i – 1}$ 修改至 $\max_i$ 或由 $\max_i$ 修改至 $\max_{i – 1}$ 。

考虑 $R$ :因为 $R$ 在块中已经排好序,所以在同一块修改完它的时间复杂度为 $O(n)$ 。对于所有块就是 $O(n\sqrt{n})$ 。

重点分析 $L$ :因为每一次改变的时间复杂度都是 $O(\max_i-\max_{i-1})$ 的,所以在同一块中时间复杂度为 $O(\sqrt{n}\cdot(\max_i-\max_{i-1}))$ 。

将每一块 $L$ 的时间复杂度合在一起,可以得到:

对于 $L$ 的总时间复杂度为

$$
\begin{aligned}
& O(\sqrt{n}(\max{} _ 1-1)+\sqrt{n}(\max{} _ 2-\max{} _ 1)+\sqrt{n}(\max{} _ 3-\max{} _ 2)+\cdots+\sqrt{n}(\max{} _ {\lceil\sqrt{n}\rceil}-\max{} _ {\lceil\sqrt{n}\rceil-1))} \\
= & O(\sqrt{n}\cdot(\max{} _ 1-1+\max{} _ 2-\max{} _ 1+\max{} _ 3-\max{} _ 2+\cdots+\max{} _ {\lceil\sqrt{n}\rceil-1}-\max{} _ {\lceil\sqrt{n}\rceil-2}+\max{} _ {\lceil\sqrt{n}\rceil}-\max{} _ {\lceil\sqrt{n}\rceil-1)}) \\
= & O(\sqrt{n}\cdot(\max{} _ {\lceil\sqrt{n}\rceil-1}))\\
\end{aligned}
$$

(裂项求和)

由题可知 $\max_{\lceil\sqrt{n}\rceil}$ 最大为 $n$ ,所以 $L$ 的总时间复杂度最坏情况下为 $O(n\sqrt{n})$ 。

综上所述,莫队算法的时间复杂度为 $O(n\sqrt{n})$ ;

但是对于 $m$ 的其他取值,如 $m<n$ ,分块方式需要改变才能变的更优。

怎么分块呢?

我们设块长度为 $S$ ,那么对于任意多个在同一块内的询问,挪动的距离就是 $n$ ,一共 $\displaystyle \frac{n}{S}$ 个块,移动的总次数就是 $\displaystyle \frac{n^2}{S}$ ,移动可能跨越块,所以还要加上一个 $mS$ 的复杂度,总复杂度为 $\displaystyle O\left(\frac{n^2}{S}+mS\right)$ ,我们要让这个值尽量小,那么就要将这两个项尽量相等,发现 $S$ 取 $\displaystyle \frac{n}{\sqrt{m}}$ 是最优的,此时复杂度为 $\displaystyle O\left(\frac{n^2}{\displaystyle \frac{n}{\sqrt{m}}}+m\left(\frac{n}{\sqrt{m}}\right)\right)=O(n\sqrt{m})$ 。

2. 例题&代码

小 Z 的袜子

传送门= ̄ω ̄=

思路:莫队算法模板题。
对于区间 $[l,r]$, 以 l 所在块的编号为第一关键字,r 为第二关键字从小到大排序。
然后从序列的第一个询问开始计算答案,第一个询问通过直接暴力算出,复杂度为 $O(n)$,后面的询问在前一个询问的基础上得到答案。

具体做法:
对于区间 $[i,i]$,由于区间只有一个元素,我们很容易就能知道答案。
然后一步一步从当前区间(已知答案)向下一个区间靠近。

我们设 $col[i]$表示当前颜色 i 出现了多少次,$ans$当前共有多少种可行的配对方案(有多少种可以选到一双颜色相同的袜子),表示然后每次移动的时候更新答案——设当前颜色为 k,如果是增长区间就是 $ans$加上 $C(col[k]+1,2)-C(col[k],2)$,如果是缩短就是 $ans$减去 $C(col[k],2)-C(col[k]-1,2)$。这应该很好理解。
而这个询问的答案就是 $ans/C(r-l+1,2)$

这里有个优化:
$C(a,2)$=$a\times (a-1)/2$
所以 $C(a+1,2)-C(a,2)$=$(a+1)\times a/2-a\times (a-1)/2$=$a/2\times (a+1-a+1)$=$a/2\times 2$=$a$
所以 $C(col[k]+1,2)-C(col[k],2)$=$col[k]$

这样我们少算了很多东西呢!
至少我的代码在 BZOJ 上测快了一倍。

还有,算 $C(a,2)$可以用位运算,$a/2$可以写成 $a>>1$。

算法总复杂度:$O(n\sqrt{n} )$

下面的代码中 mot 表示答案的分母 (mother),sub 表示分子,sqn 表示块的大小:$√n$(sqrt(n)),arr 是输入的数组,node 是存储询问的结构体,tab 是询问序列(排序后的),col 同上所述。
注意:下面代码中的移动区间的 4 个 for 循环的位置很关键,不能改变它们之间的位置关系,不然会 WA(因为有那个++l 和 — r)。

代码:

#include <bits/stdc++.h>
#define bi(a) ((a - 1) / sqn + 1)
using namespace std;
typedef long long LL;
template <typename tp>
void read(tp& dig) {
  char c = getchar();
  dig = 0;
  while (!isdigit(c)) c = getchar();
  while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
}
struct node {
  LL l, r, i;
};
LL n, m, sqn, arr[50005], l, r, ans, col[50005], sub[50005], mot[50005];
vector<node> tab;
bool cmp(node a, node b) {
  if (bi(a.l) == bi(b.l)) return a.r < b.r;
  return a.l < b.l;
}
LL gcd(LL a, LL b) { return !b ? a : gcd(b, a % b); }
int main() {
  read(n), read(m), sqn = sqrt(n);
  for (LL i = 1; i <= n; i++) read(arr[i]);
  for (LL i = 1, a, b; i <= m; i++)
    read(a), read(b), tab.push_back((node){a, b, i});
  sort(tab.begin(), tab.end(), cmp), l = r = tab[0].l, col[arr[l]]++;
  for (LL i = 0, gcdnum; i < tab.size(); i++) {
    for (; l < tab[i].l; l++) col[arr[l]]--, ans -= col[arr[l]];
    for (--l; l >= tab[i].l; l--) ans += col[arr[l]], col[arr[l]]++;
    for (; r > tab[i].r; r--) col[arr[r]]--, ans -= col[arr[r]];
    for (++r; r <= tab[i].r; r++) ans += col[arr[r]], col[arr[r]]++;
    sub[tab[i].i] = ans, l = tab[i].l, r = tab[i].r;
    mot[tab[i].i] = ((r - l) * (r - l + 1)) >> 1;
  }
  for (LL i = 1, gcdn; i <= m; i++)
    gcdn = gcd(sub[i], mot[i]),
    printf("%lld/%lld\n", sub[i] / gcdn, mot[i] / gcdn);
  return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

【算法】 树上莫队 -boshi – K-XZY · 2018年8月30日 8:09 下午

[…] 普通莫队算法教程 […]

发表回复

Avatar placeholder

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