---
tags: algorithm
---

# 莫隊(分塊算法)

若序列長度為$N$且共有$Q$筆區間詢問。

且區間之間可以正確的轉移

藉由對區間詢問進行**特別的排序**來達到一個很不錯的複雜度

## 一般莫隊

對於每一個詢問需從目前的區間$[l, r]$跑到詢問的節點$[ql, qr]$

而且從區間$[l, r]$到$[l, r + 1], [l, r - 1], [l + 1, r], [l - 1, r]$皆有$O(1)$的複雜度

可以發現，如果只是單純的進行轉移的話，對於每一筆詢問$l, r 最多皆會跑到O(N)，所以時間複雜度為O(N^2)$

那我們要怎們樣可以降低時間複雜度呢$\implies$ **分塊**

如果把$l$以$\sqrt{N}$為一塊，然後對於每一塊內對$r$進行排序
則複雜度為$O(N\sqrt{N})$

#include <bits/stdc++.h>
using namespace std;

#define F first
#define S second
int sqt;
bool cmp(pair<int,int> a ,pair<int,int> b) {
    return (a.F / sqt == b.F / sqt ? a.S < b.S : a.F < b.F);
}
int main () {
    int N; cin >> N;
    sqt = int(sqrt(N)) + 1;
    vector<pair<int,int>> query(N);
    sort(query.begin(), query.end(), cmp);
}

> 對於每一塊來說，$r$最多會從$1$跑到$N$，共有$\sqrt{N}$塊 $\implies O(N\sqrt{N})$

>在每一塊內$l$最多會跑$\sqrt{N}$次，共有$Q$筆詢問 $\implies Q\sqrt{N}$

> 總時間複雜度$O((Q + N) \sqrt{N})$

## 觀察
可以觀察到，只要從$[l, r]$轉移到$[l, r + 1], [l, r - 1], [l + 1, r], [l - 1, r]的複雜度為T，則複雜度會變為O(T\times N\sqrt{N})$

## 帶修改莫隊

只是從二維變成了三維
不過分塊的地方就不太一樣了
可以嘗試自己證證看，不過先說結論，對於$t$跟$l$來說，以$\displaystyle n^{\frac{2}{3}}$為一塊，這樣複雜度會是$O(N^{\frac{5}{3}})$

若序列長度為$N$
對於$t, l$分別以$a_1, a_2$為一塊進行排序，則複雜度為
$\displaystyle \implies a_1N + \frac{N}{a_1} (a_2N + N\times\frac{N}{a_2})$
> $t$每次最多跑$a_1$次，而對於接下來的$l, r$更新來說，最多會跑$\displaystyle \frac{N}{a_1}$次，然後就跟一般莫隊一樣，會跑$\displaystyle a_2N + N\times\frac{N}{a_2}$次

> $N \times (\displaystyle a_1 + \frac{a_2N}{a_1} + \frac{N^2}{a_1a_2})，當a_1 = a_2 = n^{\frac{2}{3}}$時複雜度會有最小值$O(N^{\frac{5}{3}})$

其實這樣的複雜度是最壞的情況下會跑到的，所以實際上的複雜度會更好。

## 結語
莫隊是一個十分優美的演算法，而且複雜度也足夠使用，程式碼也十分簡短，學起來的話在解題目時也會有別的想法。