?莫隊算法是一種離線算法，常用于高效處理區間查詢問題。它通過合理排序和移動左右端點來減少時間復雜度。

基本思想

莫隊算法的核心思想是將所有查詢離線排序！！（找出一個過起來最快的查詢順序），然后通過移動當前區間的左右端點來處理每個查詢。排序的方式通常是按照分塊（也稱為 "塊"）進行，這樣可以將時間復雜度優化到 O (n√n)。

比如，查詢（1，99）（2，7）（1，97）（3，20）

如果直接暴力，，呵呵，如果直接利用左右端點移動更新，會反復橫跳，但是如果改變查詢順序，

（2，7）（3，20）（1，97）（1，99）就不怎么跳了

ps:端點移動：就是比如你先暴力了2-7的數，并且記錄了各個數有幾次（cnt），并且保留2-7的種類數，那么接下來查詢3-20，你就可以移動左端，變成3，此時把原本2的數給減了（cnt[?]--）,如果這個減了后變成0，說明這個查詢內已經沒有這個數，就可以把種類數--了，同理，加也一樣，如果是加上變成1，說明從無到有，種類++；；；；；對于每一個查詢，維護完種類，就把當前種類記入對應的查詢原始標號內，最后依次輸出

算法步驟

1. 分塊：將數組分成若干塊，每塊大小約為√n。
2. 排序查詢：按照左端點所在塊的編號為第一關鍵字，右端點為第二關鍵字進行排序。
3. 移動端點：維護當前區間的左右端點，通過移動端點來處理每個查詢，并統計答案。

?

?這一題就是最基礎的莫隊查詢

?

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

const int maxn = 100010;

int n, m, block_size;
int a[maxn], cnt[maxn], ans[maxn];
int current_ans = 0, curL = 0, curR = 0;

struct Query {
? ? int l, r, idx;
? ? bool operator<(const Query& other) const {
? ? ? ? if (l / block_size != other.l / block_size)
? ? ? ? ? ? return l / block_size < other.l / block_size;
? ? ? ? return (l / block_size) % 2 == 0 ? r < other.r : r > other.r;
? ? }
};//利用了奇偶塊進行分塊

分塊詳解

莫隊算法的關鍵在于如何排序查詢區間，使得總移動距離最小。普通分塊策略的步驟是：

分塊：將整個數據序列分成大小為?B?的塊（通常?B ≈ √n）

排序：首先按左端點所在塊的編號排序。。如果左端點在同一塊，則按右端點排序

可見 ，分塊是為了計算出端點的范圍并打上標記，方便進行排序，進行優化計算?

bool operator<(const Query& other) const {//重定義<if (l / B != other.l / B)  // 按塊編號排序,B是預先估算的塊大小（因為通常情況大小和數量就是對n開根號，所以怎么理解都行）return l / B < other.l / B;return r < other.r;        // 左在同一塊內按右端點排序
}

普通分塊在處理同一區塊內的查詢時，右端點可能需要反復來回移動，導致額外的時間開銷。奇偶分塊優化的關鍵在于：

偶數塊：右端點按升序排列

奇數塊：右端點按降序排列

這樣處理同一區塊內的查詢時，指針移動形成 "之" 字形路徑，減少了來回跳轉的開銷。

?如：（還不如不看，自己腦子里過一遍最清晰）

Q1: [2, 10], Q2: [2, 4], Q3: [2, 7] （左端點都在塊0，偶數塊）

排序后為?Q2 → Q3 → Q1，右指針路徑：4 → 7 → 10，仍需往返。

但考慮跨塊的情況：

Q1: [2, 10]（塊0）, Q2: [5, 8]（塊1）, Q3: [5, 12]（塊1）

排序后：

偶數塊（塊 0）：Q1?[2, 10]

奇數塊（塊 1）：Q3?[5, 12]?→ Q2?[5, 8]

處理完 Q1 后，右指針在位置 10，接下來處理 Q3，右指針只需擴展到 12；處理 Q2 時收縮到 8。避免了從 10 收縮到 8 再擴展到 12 的往返操作。

?

Query queries[maxn];

inline int read() {
? ? int x = 0, f = 1; char ch = getchar();
? ? while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
? ? while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
? ? return x * f;
}

void add(int pos) {
? ? if (++cnt[a[pos]] == 1) current_ans++;//加
}

void del(int pos) {
? ? if (--cnt[a[pos]] == 0) current_ans--;//減
}

int main() {
? ? n = read(); m = read();
? ? block_size = sqrt(n);
? ??
? ? for (int i = 1; i <= n; i++)?
? ? ? ? a[i] = read();
? ??
? ? for (int i = 0; i < m; i++) {
? ? ? ? queries[i].l = read();
? ? ? ? queries[i].r = read();
? ? ? ? queries[i].idx = i;
? ? }
? ??
? ? sort(queries, queries + m);
? ? for (int i = 0; i < m; i++) {
? ? ? ? int L = queries[i].l, R = queries[i].r;
? ? ? ??
? ? ? ? while (curL > L) add(--curL);
? ? ? ? while (curR < R) add(++curR);
? ? ? ? while (curL < L) del(curL++);
? ? ? ? while (curR > R) del(curR--);//核心，一下一下移動
? ? ? ??
? ? ? ? ans[queries[i].idx] = (current_ans == (R - L + 1));

????????????????//通過和總量判斷，看看里面是不是有重復元素
? ? }
? ??
? ? for (int i = 0; i < m; i++)
? ? ? ? puts(ans[i] ? "Yes" : "No");
? ??
? ? return 0;
}

進階一點（真就一點）

完全在上一題基礎上改進

僅注解處改變

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

const int maxn = 50010;

int n, m, block_size,k;//多了個k。。。
int a[maxn];
long long current_ans = 0,ans[maxn];//因為可能很大，開了ll，這里ans們記錄的就是乘方后的維護了
int cnt[maxn], curL = 1, curR = 0;

struct Query {
?? ?int l, r, idx;
?? ?bool operator<(const Query& other) const {
?? ??? ?if (l / block_size != other.l / block_size)
?? ??? ??? ?return l / block_size < other.l / block_size;
?? ??? ?return (l / block_size) % 2 == 0 ? r < other.r : r > other.r;
?? ?}
};
Query queries[maxn];
inline int read() {
?? ?int x = 0, f = 1; char ch = getchar();
?? ?while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
?? ?while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
?? ?return x * f;
}
void add(int pos) {
?? ?if(a[pos]<=k){
?? ?current_ans-=cnt[a[pos]]*cnt[a[pos]];
?? ?++cnt[a[pos]];
?? ?current_ans+=cnt[a[pos]]*cnt[a[pos]];}
}
void del(int pos) {
?? ?if(a[pos]<=k){
?? ?current_ans-=cnt[a[pos]]*cnt[a[pos]];
?? ?--cnt[a[pos]];
?? ?current_ans+=cnt[a[pos]]*cnt[a[pos]];}//加減法都變成了對乘方的維護，而且判斷題目條件，減少計算開銷
}

int main() {
?? ?n = read(); m = read();k = read();//k
?? ?block_size = sqrt(n);
?? ?for (int i = 1; i <= n; i++)
?? ??? ?a[i] = read();
?? ?
?? ?for (int i = 0; i < m; i++) {
?? ??? ?queries[i].l = read();
?? ??? ?queries[i].r = read();
?? ??? ?queries[i].idx = i;
?? ?}
?? ?sort(queries, queries + m);
?? ?for (int i = 0; i < m; i++) {
?? ??? ?int L = queries[i].l, R = queries[i].r;
?? ??? ?while (curL > L) add(--curL);
?? ??? ?while (curR < R) add(++curR);
?? ??? ?while (curL < L) del(curL++);
?? ??? ?while (curR > R) del(curR--);

?? ??? ?ans[queries[i].idx] = current_ans;//把實時計算的乘方和映射到原始序列的數組鋰
?? ?}
?? ?
?? ?for (int i = 0; i < m; i++)
?? ??? ?printf("%lld\n",ans[i]);
?? ?return 0;
}