跳转至

普通莫隊算法

形式

假設 \(n=m\)，那麼對於序列上的區間詢問問題，如果從 \([l,r]\) 的答案能夠 \(O(1)\) 擴展到 \([l-1,r],[l+1,r],[l,r+1],[l,r-1]\)（即與 \([l,r]\) 相鄰的區間）的答案，那麼可以在 \(O(n\sqrt{n})\) 的複雜度內求出所有詢問的答案。

解釋

離線後排序，順序處理每個詢問，暴力從上一個區間的答案轉移到下一個區間答案（一步一步移動即可）。

排序方法

對於區間 \([l,r]\), 以 \(l\) 所在塊的編號為第一關鍵字，\(r\) 為第二關鍵字從小到大排序。

實現

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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))} \\ = \phantom{} & 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)}) \\ = \phantom{} & 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})\)。

事實上，如果塊長度的設定不準確，則莫隊的時間複雜度會受到很大影響。例如，如果 \(m\) 與 \(\sqrt n\) 同階，並且塊長誤設為 \(\sqrt n\)，則可以很容易構造出一組數據使其時間複雜度為 \(O(n \sqrt n)\) 而不是正確的 \(O(n)\)。

莫隊算法看起來十分暴力，很大程度上是因為莫隊算法的分塊排序方法看起來很粗糙。我們會想到通過看上去更精細的排序方法對所有區間排序。一種方法是把所有區間 \([l, r]\) 看成平面上的點 \((l, r)\)，並對所有點建立曼哈頓最小生成樹，每次沿着曼哈頓最小生成樹的邊在詢問之間轉移答案。這樣看起來可以改善莫隊算法的時間複雜度，但是實際上對詢問分塊排序的方法的時間複雜度上界已經是最優的了。

假設 \(n, m\) 同階且 \(n\) 是完全平方數。我們考慮形如 \([a \sqrt n, b \sqrt n](1 \le a, b \le \sqrt n)\) 的區間，這樣的區間一共有 \(n\) 個。如果把所有的區間看成平面上的點，則兩點之間的曼哈頓距離恰好為兩區間的轉移代價，並且任意兩個區間之間的最小曼哈頓距離為 \(\sqrt n\)，所以處理所有詢問的時間複雜度最小為 \(O(n \sqrt n)\)。其它情況的數據構造方法與之類似。

莫隊算法還有一個特點：當 \(n\) 不變時，\(m\) 越大，處理每次詢問的平均轉移代價就越小。一些其他的離線算法也具有同樣的特點（如求 LCA 的 Tarjan 算法），但是莫隊算法的平均轉移代價隨 \(m\) 的變化最明顯。

例題 & 代碼

例題 「國家集訓隊」小 Z 的襪子

題目大意：

有一個長度為 \(n\) 的序列 \(\{c_i\}\)。現在給出 \(m\) 個詢問，每次給出兩個數 \(l,r\)，從編號在 \(l\) 到 \(r\) 之間的數中隨機選出兩個不同的數，求兩個數相等的概率。

過程

思路：莫隊算法模板題。

對於區間 \([l,r]\)，以 \(l\) 所在塊的編號為第一關鍵字，\(r\) 為第二關鍵字從小到大排序。

然後從序列的第一個詢問開始計算答案，第一個詢問通過直接暴力算出，複雜度為 \(O(n)\)，後面的詢問在前一個詢問的基礎上得到答案。

具體做法：

對於區間 \([i,i]\)，由於區間只有一個元素，我們很容易就能知道答案。然後一步一步從當前區間（已知答案）向下一個區間靠近。

我們設 \(col[i]\) 表示當前顏色 \(i\) 出現了多少次，\(ans\) 當前共有多少種可行的配對方案（有多少種可以選到一雙顏色相同的襪子），表示然後每次移動的時候更新答案——設當前顏色為 \(k\)，如果是增長區間就是 \(ans\) 加上 \(\dbinom{col[k]+1}{2}-\dbinom{col[k]}{2}\)，如果是縮短就是 \(ans\) 減去 \(\dbinom{col[k]}{2}-\dbinom{col[k]-1}{2}\)。

而這個詢問的答案就是 \(\displaystyle \frac{ans}{\dbinom{r-l+1}{2}}\)。

這裏有個優化：\(\displaystyle \dbinom{a}{2}=\frac{a (a-1)}{2}\)。

所以 \(\displaystyle \dbinom{a+1}{2}-\dbinom{a}{2}=\frac{(a+1) a}{2}-\frac{a (a-1)}{2}=\frac{a}{2}\cdot (a+1-a+1)=\frac{a}{2}\cdot 2=a\)。

所以 \(\dbinom{col[k]+1}{2}-\dbinom{col[k]}{2}=col[k]\)。

算法總複雜度：\(O(n\sqrt{n} )\)

下面的代碼中 deno 表示答案的分母 (denominator)，nume 表示分子 (numerator)，sqn 表示塊的大小：\(\sqrt{n}\)，arr 是輸入的數組，node 是存儲詢問的結構體，tab 是詢問序列（排序後的），col 同上所述。

注意：由於 ++l 和 --r 的存在，下面代碼中的移動區間的 4 個 while 循環的位置很關鍵，不能隨意改變它們之間的位置關係。

關於四個循環位置的討論

莫隊區間的移動過程，就相當於加入了 \([1,r]\) 的元素，並刪除了 \([1,l-1]\) 的元素。因此，

  • 對於 \(l\le r\) 的情況，\([1,l-1]\) 的元素相當於被加入了一次又被刪除了一次，\([l,r]\) 的元素被加入一次，\([r+1,+\infty)\) 的元素沒有被加入。這個區間是合法區間。
  • 對於 \(l=r+1\) 的情況，\([1,r]\) 的元素相當於被加入了一次又被刪除了一次，\([r+1,+\infty)\) 的元素沒有被加入。這時這個區間表示空區間。
  • 對於 \(l>r+1\) 的情況，那麼 \([r+1,l-1]\)（這個區間非空）的元素被刪除了一次但沒有被加入，因此這個元素被加入的次數是負數。

因此，如果某時刻出現 \(l>r+1\) 的情況，那麼會存在一個元素，它的加入次數是負數。這在某些題目會出現問題，例如我們如果用一個 set 維護區間中的所有數，就會出現「需要刪除 set 中不存在的元素」的問題。

代碼中的四個 while 循環一共有 \(4!=24\) 種排列順序。不妨設第一個循環用於操作左端點，就有以下 \(12\) 種排列（另外 \(12\) 種是對稱的）。下表列出了這 12 種寫法的正確性，還給出了錯誤寫法的反例。

循環順序 正確性 反例或註釋
l--,l++,r--,r++ 錯誤 \(l<r<l'<r'\)
l--,l++,r++,r-- 錯誤 \(l<r<l'<r'\)
l--,r--,l++,r++ 錯誤 \(l<r<l'<r'\)
l--,r--,r++,l++ 正確 證明較繁瑣
l--,r++,l++,r-- 正確
l--,r++,r--,l++ 正確
l++,l--,r--,r++ 錯誤 \(l<r<l'<r'\)
l++,l--,r++,r-- 錯誤 \(l<r<l'<r'\)
l++,r++,l--,r-- 錯誤 \(l<r<l'<r'\)
l++,r++,r--,l-- 錯誤 \(l<r<l'<r'\)
l++,r--,l--,r++ 錯誤 \(l<r<l'<r'\)
l++,r--,r++,l-- 錯誤 \(l<r<l'<r'\)

全部 24 種排列中只有 6 種是正確的，其中有 2 種的證明較繁瑣，這裏只給出其中 4 種的證明。

這 4 種正確寫法的共同特點是，前兩步先擴大區間（l-- 或 r++），後兩步再縮小區間（l++ 或 r--）。這樣寫，前兩步是擴大區間，可以保持 \(l\le r+1\)；執行完前兩步後，\(l\le l'\le r'\le r\) 一定成立，再執行後兩步只會把區間縮小到 \([l',r']\)，依然有 \(l\le r+1\)，因此這樣寫是正確的。

實現

參考代碼 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <algorithm>
#include <cmath>
#include <cstdio>
using namespace std;
const int N = 50005;
int n, m, maxn;
int c[N];
long long sum;
int cnt[N];
long long ans1[N], ans2[N];

struct query {
  int l, r, id;

  bool operator<(const query &x) const {  // 重载<运算符
    if (l / maxn != x.l / maxn) return l < x.l;
    return (l / maxn) & 1 ? r < x.r : r > x.r;
  }
} a[N];

void add(int i) {
  sum += cnt[i];
  cnt[i]++;
}

void del(int i) {
  cnt[i]--;
  sum -= cnt[i];
}

long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }

int main() {
  scanf("%d%d", &n, &m);
  maxn = sqrt(n);
  for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
  for (int i = 0; i < m; i++) scanf("%d%d", &a[i].l, &a[i].r), a[i].id = i;
  sort(a, a + m);
  for (int i = 0, l = 1, r = 0; i < m; i++) {  // 具体实现
    if (a[i].l == a[i].r) {
      ans1[a[i].id] = 0, ans2[a[i].id] = 1;
      continue;
    }
    while (l > a[i].l) add(c[--l]);
    while (r < a[i].r) add(c[++r]);
    while (l < a[i].l) del(c[l++]);
    while (r > a[i].r) del(c[r--]);
    ans1[a[i].id] = sum;
    ans2[a[i].id] = (long long)(r - l + 1) * (r - l) / 2;
  }
  for (int i = 0; i < m; i++) {
    if (ans1[i] != 0) {
      long long g = gcd(ans1[i], ans2[i]);
      ans1[i] /= g, ans2[i] /= g;
    } else
      ans2[i] = 1;
    printf("%lld/%lld\n", ans1[i], ans2[i]);
  }
  return 0;
}

普通莫隊的優化

過程

我們看一下下面這組數據

1
2
3
4
5
// 設塊的大小為 2 (假設)
1 1
2 100
3 1
4 100

手動模擬一下可以發現，r 指針的移動次數大概為 300 次，我們處理完第一個塊之後，\(l = 2, r = 100\)，此時只需要移動兩次 l 指針就可以得到第四個詢問的答案，但是我們卻將 r 指針移動到 1 來獲取第三個詢問的答案，再移動到 100 獲取第四個詢問的答案，這樣多了九十幾次的指針移動。我們怎麼優化這個地方呢？這裏我們就要用到奇偶化排序。

什麼是奇偶化排序？奇偶化排序即對於屬於奇數塊的詢問，r 按從小到大排序，對於屬於偶數塊的排序，r 從大到小排序，這樣我們的 r 指針在處理完這個奇數塊的問題後，將在返回的途中處理偶數塊的問題，再向 n 移動處理下一個奇數塊的問題，優化了 r 指針的移動次數，一般情況下，這種優化能讓程序快 30% 左右。

實現

排序代碼：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
// 這裏有個小細節等下會講
int unit;  // 塊的大小

struct node {
  int l, r, id;

  bool operator<(const node &x) const {
    return l / unit == x.l / unit
               ? (r == x.r ? 0 : ((l / unit) & 1) ^ (r < x.r))
               : l < x.l;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
struct node {
  int l, r, id;

  bool operator<(const node &x) const {
    if (l / unit != x.l / unit) return l < x.l;
    // 注意下面兩行不能寫小於（大於）等於，否則會出錯（詳見下面的小細節）
    if ((l / unit) & 1) return r < x.r;
    return r > x.r;
  }
};
小細節

如果使用 sort 比較兩個結構體，不能出現 \(a < b\) 和 \(b < a\) 同時為真的情況，否則會運行錯誤，詳見 常見錯誤。

對於壓行版，如果沒有 r == x.r 的特判，當 l 屬於同一奇數塊且 r 相等時，會出現上面小細節中的問題（自己手動模擬一下），對於不壓行版，如果寫成小於（大於）等於，則也會出現同樣的問題。

參考資料

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：StudyingFather, Backl1ght, countercurrent-time, Ir1d, greyqz, MicDZ, ouuan
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用