莫队算法是一种离线算法，常用于高效处理区间查询问题。它通过合理排序和移动左右端点来减少时间复杂度。

基本思想

莫队算法的核心思想是将所有查询离线排序！！（找出一个过起来最快的查询顺序），然后通过移动当前区间的左右端点来处理每个查询。排序的方式通常是按照分块（也称为 "块"）进行，这样可以将时间复杂度优化到 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;
}