终于补完离线算法了（
莫队是三大离线算法之一（毒瘤且少用的线段树分治不算），同时也是许多人入坑的第一种离线算法。虽然思路比较简单，但是莫队题型多、容易出错、写代码时常常粗心，部分理论可能难以理解，本创作计划旨在帮助读者完善莫队知识盲点、学习带修和回滚莫队的思想（因为网上的资源比较难懂，本人也曾深受其害）。
关于莫队，有个特点是代码比较好写，常数也很小。难绷三大离线算法两个（莫队和整体二分）常数小得逆天容易跑得比同复杂度甚至更优复杂度解法快还特别适合 O2 一个（CDQ 分治）就常数大（使用大量 sort 的话还会明显变慢）然后天天被 K-D 树和多维分块（WorldMachine%%%)打压。

莫队是什么

莫队算法是由莫涛提出的算法．在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人．莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本.
莫队算法可以解决一类离线区间询问问题，适用性极为广泛．同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作．(from OI-wiki)

从一道模板题入手。

P2709 【模板】莫队 / 小B的询问

题目描述

小 B 有一个长为 $n$ 的整数序列 $a$，值域为 $[1,k]$。
他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$，求：

$$\sum\limits_{i=1}^k c_i^2$$

其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。
小 B 请你帮助他回答询问。

输入格式

第一行三个整数 $n,m,k$。
第二行 $n$ 个整数，表示小 B 的序列。
接下来的 $m$ 行，每行两个整数 $l,r$。

输出格式

输出 $m$ 行，每行一个整数，对应一个询问的答案。

说明/提示

【数据范围】
对于 $100\%$ 的数据，$1\le n,m,k \le 5\times 10^4$。

总之就是询问你一个区间里每个数出现次数的平方加起来是多少。
这题维护的东西用普通 ds 和算法维护看上去很不可做。如果用暴力呢？
我们只需要定义一个 cnt 数组，定义 $cnt_i$ 表示数值 i 在序列中出现的次数。当加入一个新数时，把当前答案加上这个原来出现的次数再 +1 就行了。很容易证明正确性。但是这样复杂度是 $O(NM)$.
而莫队算法仅用了一个排序的技巧，就优化了时间复杂度。如何做到？
首先，假设我们有大量询问：

（画得丑致歉）
注意到不同区间有很多重复的地方，在询问中会被重复计算，这个地方能不能节省呢？
先看看以下情况：

只需要将粉色区间左端点略微右移，右端点也右移就与绿色区间一样了。
莫队为了节省这些计算，将数列分为 $\sqrt N$ 块（假设 N=M)，每一块长度为 $\sqrt N$.接下来对询问进行排序，将询问按左端点所在的块从左到右排序，左端点所在块一样则按右端点升序排序。然后按照排序顺序从前到后处理询问，存储上一次询问的左端点和右端点，并对其进行移动使得左端点和右端点与当前询问吻合，然后存储当前答案。
对于本题，左端点和右端点的移动都是 $O(1)$ 的。
时间复杂度是多少？
每次处理新的询问，左端点和右端点都会进行移动。对于左端点的移动，由于对左端点所在块排序，所以一个块内询问左端点的移动一次是 $O(\sqrt N)$. 如果要到右边的块，由于一个块长度为 $\sqrt N$ , 也只需要 $O(\sqrt N)$ 的时间复杂度进行一次移动。总共进行 M 次移动，因此所有左端点移动的时间复杂度是 $O(M\sqrt N)$.

那么右端点的移动呢？对于每个块内的询问，右端点是从小到大递增的，所以一个块内右端点的移动共为 N 次，总共有 $\sqrt N$ 个块，所以移动右端点的时间复杂度为 $O(N\sqrt N)$.

两者相加，$O(M\sqrt N)+O(N\sqrt N)=O(N\sqrt N)$（N=M)
本题要怎么移动左端点和右端点？当左端点向左时，新添加的数 x 给答案做的贡献是 $(cnt_x+1)^2-cnt_x^2=2\times cnt_x+1$, 因此我们先将答案加上 $2\times cnt_x+1$, 再更新 cnt 数组即可。其它移动操作自己推。
本题数据为 $1\le n,m,k \le 5\times 10^4$, 时间复杂度正确。
小优化：大部分莫队可以用奇偶性优化减少常数。对于左端点为第奇数块的询问，右端点从左到右排，否则从右到左排。如图所示：

注：实际上是曼哈顿距离，这里为了方便画的是欧式距离。
这个优化最多优化一半的计算量，一般可以提升几十毫秒的速度，但是也有一些数据反而会跑更久。
还有一点需要注意：初始 l=1,r=0. 记住，当莫队需要在 x 和 x+1 直接设置初始位置并向左右分别扩展时，l=x+1,r=x.
以下是本题代码：

#include<bits/stdc++.h>
using namespace std;
int n,a[50005],m,t,k,c[50005],sum,ans[50005];
struct q{
    int l,r,id;
}qry[50005];
bool cmp(q a,q b){
    if((a.l-1)/t!=(b.l-1)/t)return (a.l-1)/t<(b.l-1)/t;
    if(((a.l-1)/t)&1)return a.r<b.r;
    return a.r>b.r;
}
void del(int x){
    sum-=c[a[x]]*2-1;
    c[a[x]]--;
}
void add(int x){
    c[a[x]]++;
    sum+=c[a[x]]*2-1;
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
int main(){
    n=read(),m=read(),k=read(),t=sqrt(m);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i)qry[i]={read(),read(),i};
    sort(qry+1,qry+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;++i){
        while(qry[i].l<L)add(--L);
        while(R<qry[i].r)add(++R);
        while(L<qry[i].l)del(L++);
        while(qry[i].r<R)del(R--);
        ans[qry[i].id]=sum;
    }
    for(int i=1;i<=m;++i)write(ans[i]),putchar('\n');
    return 0;
}

这段代码采用的是莫队常用的写法，其中 &1 可以判断一个数是否为奇数。
请对照模板题代码自己理解。

莫队分块

当 N=M 时，分块大小为 $\sqrt N$ 最优。但是当 $N\neq M$ 时，分块为 $\frac{N}{\sqrt M}$ 是最优的。这时候左端点移动复杂度为 $O(M\times \frac{N}{\sqrt M})=O(N\sqrt M)$, 右端点移动复杂度为 $O(\sqrt M\times N)=O(N\sqrt M)$, 总时间复杂度为 $O(N\sqrt M)$

普通莫队例题

P1494 [国家集训队] 小 Z 的袜子

自行看题。
如何回答询问？我们需要知道区间内每一种颜色的袜子抽到一样的方案数，除以区间总方案数。区间总方案数的计算是入门的。很明显我们要维护 $\frac{cnt_x\times (cnt_x-1)}{2}$. 最后那个 $\frac{1}{2}$ 不用维护，因为会约分所以只要总方案数也不乘以 $\frac{1}{2}$ 就能抵消了。像上题一样维护 $cnt_x^2$ 就行了，维护完还要对每个 $x$ 减去 $cnt_x$（由上式可知）, 由于一个区间里所有出现数值 $x$ 的出现次数之和就是这个区间的长度，因此求出 $\sum{}^{}cnt_x$ 后直接减去区间大小即可。每个查询算完还要进行约分，但是约分时间复杂度较小直接并入总复杂度。以下代码进行了特判，但是似乎这个方法实现不需要特判。
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[50005],m,t,c[50005],sum,aa[50005],bb[50005];
struct q{
    int l,r,id;
}qry[50005];
bool cmp(q a,q b){
    if((a.l-1)/t!=(b.l-1)/t)return (a.l-1)/t<(b.l-1)/t;
    if(((a.l-1)/t)&1)return a.r<b.r;
    return a.r>b.r;
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
signed main(){
    n=read(),m=read(),t=sqrt(m);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i)qry[i]={read(),read(),i};
    sort(qry+1,qry+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;++i){
        while(qry[i].l<L)--L,c[a[L]]++,sum+=(c[a[L]]<<1)-1;
        while(R<qry[i].r)++R,c[a[R]]++,sum+=(c[a[R]]<<1)-1;
        while(L<qry[i].l)c[a[L]]--,sum-=(c[a[L]]<<1)+1,++L;
        while(qry[i].r<R)c[a[R]]--,sum-=(c[a[R]]<<1)+1,--R;
        if(qry[i].l==qry[i].r){aa[qry[i].id]=0,bb[qry[i].id]=1;continue;}
        aa[qry[i].id]=sum-(qry[i].r-qry[i].l+1);
        bb[qry[i].id]=(qry[i].r-qry[i].l+1)*(qry[i].r-qry[i].l);
        int tmp=__gcd(aa[qry[i].id],bb[qry[i].id]);
        aa[qry[i].id]/=tmp,bb[qry[i].id]/=tmp;
    }
    for(int i=1;i<=m;++i)write(aa[i]),putchar('/'),write(bb[i]),putchar('\n');
    return 0;
}

P1997 faebdc 的烦恼

本题其实就是让你求区间众数出现的次数。
普通莫队似乎不能维护删除操作，因为区间众数是回滚莫队才能维护的。但是，不要小看普通莫队啊！
设 maxn 为答案，每个询问不重置 maxn, 仅改动 maxn. 加入操作可以通过 c(cnt) 数组直接维护最大值。那么删除操作如何实现？设 $cc_i$ 为 i 在 c 中出现的次数，删除第 i 个数字时如果 $cc_{c_i}＞1$ 则直接将 $cc_{c_i}$ 减一， $c_i$ 更新后再将当前 $cc_{c_i}$ 加一。当删除元素等于众数且众数只有一个时，依旧维护以上两个数组并将 maxn 减一，因为原来的众数都没了，刚刚删掉一个原来出现了 maxn 次的众数，所以现在这个数出现的次数为 maxn-1.
$Code:$

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],m,t,c[200005],maxn,ans[200005],rec[200005];
struct q{
    int l,r,id;
}qry[200005];
bool cmp(q a,q b){
    if((a.l-1)/t!=(b.l-1)/t)return (a.l-1)/t<(b.l-1)/t;
    if(((a.l-1)/t)&1)return a.r<b.r;
    return a.r>b.r;
}
void del(int x){
    maxn-=(rec[c[a[x]]]==1&&maxn==c[a[x]]),--rec[c[a[x]]--];
}
void add(int x){rec[++c[a[x]]]++;maxn=max(maxn,c[a[x]]);}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
int main(){
    n=read(),m=read(),t=sqrt(m);
    for(int i=1;i<=n;++i)a[i]=read()+100001;
    for(int i=1;i<=m;++i)qry[i]={read(),read(),i};
    sort(qry+1,qry+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;++i){
        while(qry[i].l<L)add(--L);
        while(R<qry[i].r)add(++R);
        while(L<qry[i].l)del(L++);
        while(qry[i].r<R)del(R--);
        ans[qry[i].id]=maxn;
    }
    for(int i=1;i<=m;++i)write(ans[i]),putchar('\n');
    return 0;
}

P11659 小夫

注意到出题人又让我们维护不是人的东西了，所以容易联想到莫队。怎么维护呢？
维护三个数组：cnt,cnt42,cnt23.
$cnt_i$ 表示 i 在区间内出现的次数，$cnt42_i$ 表示序列中 $l\le x<y\le r,a_x=4\times i,a_y=2\times i$ 的二元组数量， $cnt23_i$ 表示序列中 $l\le x<y\le r,a_x=2\times i,a_y=3\times i$ 的二元组数量。
左端点左移时，加入一个数，先不更新 cnt(因为要用到原来序列的 cnt) ,如果 $a_l$ 可以被 4 整除，$cnt42_{\frac{a_l}{4}}$ 要加上与 $a_l$ 符合 4:2 比的数的个数，即 $cnt_{\frac{a_l}{2}}$, 同时也更新答案，将答案加上 $cnt23_{\frac{a_l}{4}}$. 如果 $a_l$ 可以被 2 整除，$cnt23_{\frac{a_l}{2}}$ 要加上 $cnt_{a_l\times \frac{3}{2}}$. 其它操作也按这个原理做，注意删除操作要先更新 cnt.
注：数组要开两倍，自己想为什么。
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[200005],m,t,cnt42[400005],cnt23[400005],cnt[400005],ans[200005],sum;
struct qry{
    int l,r,id;
}q[200005];
bool cmp(qry a,qry b){return ((a.l-1)/t^(b.l-1)/t)?(a.l-1)/t<(b.l-1)/t:(((a.l-1)/t)&1?a.r<b.r:a.r>b.r);}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),m=read(),t=sqrt(n);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i)q[i]={read(),read(),i};
    sort(q+1,q+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;++i){
        while(q[i].l<L){
            --L;
            if(a[L]%4==0)sum+=cnt23[a[L]/4],cnt42[a[L]/4]+=cnt[a[L]/2];
            if(a[L]%2==0)cnt23[a[L]/2]+=cnt[a[L]/2*3];
            cnt[a[L]]++;
        }
        while(R<q[i].r){
            ++R;
            if(a[R]%3==0)sum+=cnt42[a[R]/3],cnt23[a[R]/3]+=cnt[a[R]/3*2];
            if(a[R]%2==0)cnt42[a[R]/2]+=cnt[a[R]*2];
            cnt[a[R]]++;
        }
        while(L<q[i].l){
            cnt[a[L]]--;
            if(a[L]%4==0)sum-=cnt23[a[L]/4],cnt42[a[L]/4]-=cnt[a[L]/2];
            if(a[L]%2==0)cnt23[a[L]/2]-=cnt[a[L]/2*3];
            ++L;
        }
        while(q[i].r<R){
            cnt[a[R]]--;
            if(a[R]%3==0)sum-=cnt42[a[R]/3],cnt23[a[R]/3]-=cnt[a[R]/3*2];
            if(a[R]%2==0)cnt42[a[R]/2]-=cnt[a[R]*2];
            --R;
        }
        ans[q[i].id]=sum;
    }
    for(int i=1;i<=m;++i)write(ans[i]),putchar_unlocked('\n');
    return 0;
}

经过以上锻炼，可以发现莫队的优势是可以维护其它东西很难维护的条件，但是相对应的，莫队是一个离线、不便于修改的算法，具有一定的局限性。

带修莫队

带修莫队有什么用基本没题考
以上的莫队都是只查询不修改的。那要是加上单点修改呢？
对于 CDQ 分治有大量经验的你可能会想到，把时间也看成一个维度进行排序不就行了？将询问进行排序，然后左端点、右端点、时间一起移动成当前询问。时间移动时如果往后移动就按顺序修改，往前就倒序回溯过去。
带修莫队的操作是将元素按左端点所在块排序，一样则按右端点所在块排序，还是一样就按时间从小到大排（一个询问的时间为这个询问前面进行的修改操作的数量）。
但是分块显然要改了，因为如果还是按原来分的话时间维度的总移动复杂度是 $O(NM)$ ，显然这不是我们想要的。这个时候你会干什么呢？

当块长为 $N^{\frac{2}{3}}$ 时，左端点移动的时间复杂度是 $O(N^{\frac{2}{3}}\times M)=O(MN^\frac{2}{3})$, 右端点移动一样是 $O(MN^\frac{2}{3})$, 时间移动是 $O(N^{\frac{1}{3}}\times N^{\frac{1}{3}}\times M)=O(MN^\frac{2}{3})$, 所以总的时间复杂度还是 $O(MN^\frac{2}{3})$.
例题：P1903 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列
直接上代码。注意本题的单点修改直接将 $a_{c_{i,p}}$ 与 $c_{i,col}$ 交换（把要修改的原位置值和修改操作的新值调换），这和人不能连续向一个方向跨过同一条河流是一个道理，当你执行了一次修改操作后当前时间就会大于这个操作的所在时间，所以下一次调用这个函数只有一种可能：当前时间在减小，即时间回溯操作，这时候再调换回来即可。
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1000005;
int n,m,b,cnt[N],a[N],ans[N],res,L=1,R=0,cntc,cntq,t;char op;
struct mfy{int p,col;}c[N];
struct qry{
    int l,r,t,id;
    bool operator<(const qry &y)const{return l/b!=y.l/b?l<y.l:(r/b!=y.r/b?r<y.r:((r/b)&1?t<y.t:t>y.t));}
}q[N];
void add(int x){if(!cnt[x]++)++res;}
void del(int x){if(!--cnt[x])--res;}
void modify(int x,int T){
    if(q[x].l<=c[T].p&&c[T].p<=q[x].r)del(a[c[T].p]),add(c[T].col);
    swap(a[c[T].p],c[T].col);
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),m=read();
    b=pow(n,2.0/3.0);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i){
        cin>>op;
        if(op=='Q')q[++cntq]={read(),read(),cntc,cntq};
        else c[++cntc]={read(),read()};
    }
    sort(q+1,q+cntq+1);
    for(int i=1;i<=cntq;++i){
        while(L<q[i].l)del(a[L++]);
        while(L>q[i].l)add(a[--L]);
        while(R<q[i].r)add(a[++R]);
        while(R>q[i].r)del(a[R--]);
        while(t<q[i].t)modify(i,++t);
        while(t>q[i].t)modify(i,t--);
        ans[q[i].id]=res;
    }
    for(int i=1;i<=cntq;++i)
        write(ans[i]),putchar('\n');
    return 0;
}

带修莫队似乎没什么用同时这题还有 $O(Nlog^2N)$ 的树套树和 CDQ 分治解法，学习了 CDQ 分治的读者可以尝试，因为这题其实就是P4690 [Ynoi Easy Round 2016] 镜中的昆虫的弱化版。虽然是 Ynoi easy round 的……

（偷图致歉）

回滚莫队

他们说回滚莫队没用，我觉得有用。
回滚莫队有两种：不删除莫队（有点用）和不添加莫队（有存在必要吗）。不添加莫队我没见过题，更不会做，也不会写，所以不讲，知道怎么计算初始整体状态并且能翻到例题的请容我%%%。
不删除莫队用于莫队算法添加容易删除难的情况。以下是例题：
P14420 [JOISC 2014] 历史的研究 / Historical Research
题目要你求序列内一个数的值乘以这个数出现次数的积的最大值。添加元素只需要将出现次数更新然后取答案最大值就行了。如何删除？
不删除！
接下来我们使用显性分块编码，存储每个位置所在块和每个块的左右端点。
先假设我们的所有询问左右端点都在不同的块上，即右端点所在块在左端点所在块右边。
回滚莫队遍历每一个块，一开始将 l 设为这个块右端点位置+1，r 设在右端点。

然后先扩展右端点。

我们将这个答案保存，然后扩展左端点。

这时候记录答案。这时候，我们将 l 一步步右移，把辅助数组回溯成原来的样子。注意，是回溯不是删除（因为答案没有更改）。

到了下一个询问，初始答案直接设为上次保存的答案就行了，然后在区间基础上扩展右端点，因为右端点是递增的只需要添加，情况又回到了一开始。以此类推，这个块算完了就跳到下一个块。整个过程只用了添加和回溯操作，答案不通过回溯更新（因为答案更新更难）而是直接用上次答案。注意到回溯操作根本不用复杂维护，只要你能确保辅助数组回到上次状态就行。
时间复杂度是多少？左端点的移动一次 $O(\sqrt N)$, 右端点也没变，所以还是 $O(N\sqrt N)$ 的时间复杂度。
等等，那左右端点在同一块的询问呢？直接暴力就行了，因为这时候一次暴力 $O(\sqrt N)$.
很容易想到，回滚莫队自然不能用奇偶性优化了。
对于这道例题，我们依旧 cnt 数组，扩展时先更新 cnt 再更新最大值，回溯 cnt 时遇到一个就将它的 cnt 减去 1. 暴力是有手就行的。其实这题就是一道变形的区间众数。
注意看 $Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int n,m,tot,B,T,b[N],cnt[N],a[N],ans[N],c[N],res,L,R,tmp,cur,bl[N],br[N],be[N];
struct qry{
    int l,r,id;
    bool operator<(const qry &y)const{return (be[l]^be[y.l])?l<y.l:r<y.r;}
}q[N];
int bf(int l,int r){
    int ans=0;
    for(int i=l;i<=r;++i)++c[a[i]];
    for(int i=l;i<=r;++i)ans=max(ans,c[a[i]]*b[a[i]]);
    for(int i=l;i<=r;++i)--c[a[i]];
    return ans;
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),m=read(),T=sqrt(n),B=n/T;
    for(int i=1;i<=n;++i)a[i]=b[i]=read();
    for(int i=1;i<=m;++i)q[i]={read(),read(),i};
    sort(b+1,b+n+1),tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    for(int i=1;i<=B;++i)bl[i]=br[i-1]+1,br[i]=bl[i]+T-1;
    if(br[B]<n)++B,bl[B]=br[B-1]+1,br[B]=n;
    for(int i=1;i<=n;++i)be[i]=(i-1)/T+1;
    sort(q+1,q+m+1);
    for(int i=1,idx=1;i<=B;++i){
        memset(cnt,0,sizeof cnt);
        R=br[i];
        tmp=0;
        while(be[q[idx].l]==i){
            L=br[i]+1;
            if(q[idx].r-q[idx].l<=T){
                ans[q[idx].id]=bf(q[idx].l,q[idx].r);
                ++idx;
                continue;
            }
            while(q[idx].r>R)++R,tmp=max(tmp,(++cnt[a[R]])*b[a[R]]);
            cur=tmp;
            while(q[idx].l<L)--L,tmp=max(tmp,(++cnt[a[L]])*b[a[L]]);
            ans[q[idx].id]=tmp;
            tmp=cur;
            while(L<=br[i])--cnt[a[L++]];
            ++idx;
        }
    }
    for(int i=1;i<=m;++i)write(ans[i]),putchar('\n');
    return 0;
}

闲话：这个模板也是我选的而不是洛谷官方模板，回滚莫队和线段树合并一样都是有一道题既用到知识点又最简单然后被推崇为模板但是官方模板却要经过一定的思考。不过雨天的尾巴这个名字好好听啊你值得模板之名QvQ.
既然已经做出了这道题那么区间众数也很简单了：

P13984 数列分块入门 9

回滚莫队入门9（误）
所以 Ynoi 是不是叫数列分块提高
更新答案时就不用乘以这个数的值了。注意到要求出现次数一样时答案为最小者，所以要保存两个答案：答案出现次数和答案数值大小，方便比较更新。
同时此题告诉我一个很重要的点：调回滚莫队一定要把每次遍历块时初始化的那个（些）变量当作实际维护的答案，不要当成中间值变量。小朋友们不要忘记一开始初始化辅助数组哦。
此题套模板做的 6 分钟一道紫我太强了
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=600005;
int n,tot,B,T,b[N],cnt[N],a[N],ans[N],c[N],L,R,tmp,cur,num,tmpnum,bl[N],br[N],be[N];
struct qry{
    int l,r,id;
    bool operator<(const qry &y)const{return (be[l]^be[y.l])?l<y.l:r<y.r;}
}q[N];
int bf(int l,int r){
    int ans=2e9,num=0;
    for(int i=l;i<=r;++i)++c[a[i]];
    for(int i=l;i<=r;++i)if(num<c[a[i]]||(num==c[a[i]]&&a[i]<ans))num=c[a[i]],ans=a[i];
    for(int i=l;i<=r;++i)--c[a[i]];
    return ans;
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),T=sqrt(n),B=n/T;
    for(int i=1;i<=n;++i)a[i]=b[i]=read();
    for(int i=1;i<=n;++i)q[i]={read(),read(),i};
    sort(b+1,b+n+1),tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    for(int i=1;i<=B;++i)bl[i]=br[i-1]+1,br[i]=bl[i]+T-1;
    if(br[B]<n)++B,bl[B]=br[B-1]+1,br[B]=n;
    for(int i=1;i<=n;++i)be[i]=(i-1)/T+1;
    sort(q+1,q+n+1);
    for(int i=1,idx=1;i<=B;++i){
        memset(cnt,0,sizeof cnt);
        R=br[i];
        tmp=2e9,tmpnum=0;
        while(idx<=n&&be[q[idx].l]==i){
            L=br[i]+1;
            if(q[idx].r-q[idx].l<=T){
                ans[q[idx].id]=bf(q[idx].l,q[idx].r);
                ++idx;
                continue;
            }
            while(q[idx].r>R){++cnt[a[++R]];if(tmpnum<cnt[a[R]]||(tmpnum==cnt[a[R]]&&a[R]<tmp))tmpnum=cnt[a[R]],tmp=a[R];}
            cur=tmp,num=tmpnum;
            while(q[idx].l<L){++cnt[a[--L]];if(tmpnum<cnt[a[L]]||(tmpnum==cnt[a[L]]&&a[L]<tmp))tmpnum=cnt[a[L]],tmp=a[L];}
            ans[q[idx].id]=tmp;
            tmp=cur,tmpnum=num;
            while(L<=br[i])--cnt[a[L++]];
            ++idx;
        }
    }
    for(int i=1;i<=n;++i)write(b[ans[i]]),putchar('\n');
    return 0;
}

此题的效率也跑到了一个丧心病狂的程度：

接下来是真正的模板题：

P5906 【模板】回滚莫队&不删除莫队

本题独立 3 分钟解出来我太强了我要进省队了
这题可以维护 4 个数组，左端点左移遇到的某数的最左值、左端点右移遇到的某数的最右值、右端点左移遇到的某数的最左值、右端点右移遇到的某数的最右值，最左/最右取左右端点答案的最值即可得到，记得要初始化数组，回溯时将左端点遇到的最左和最右端的值都回溯成初始化时的状态即可。当然我还开了两个数组进行暴力。不会你们学回滚莫队尝试自己默时忘记写暴力了吧。
$Code:$

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=200005;
int n,m,tot,B,T,b[N],str[N],edr[N],stl[N],edl[N],a[N],ans[N],st[N],ed[N],res,L,R,tmp,cur,bl[N],br[N],be[N];
struct qry{
    int l,r,id;
    bool operator<(const qry &y)const{return (be[l]^be[y.l])?l<y.l:r<y.r;}
}q[N];
int bf(int l,int r){
    int ans=0;
    for(int i=l;i<=r;++i)st[a[i]]=min(st[a[i]],i),ed[a[i]]=max(ed[a[i]],i),ans=max(ans,ed[a[i]]-st[a[i]]);   
    for(int i=l;i<=r;++i)st[a[i]]=2e9,ed[a[i]]=0;
    return ans;
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
signed main(){
    n=read(),T=sqrt(n),B=n/T;
    for(int i=1;i<=n;++i)a[i]=b[i]=read();
    m=read();
    for(int i=1;i<=m;++i)q[i]={read(),read(),i};
    sort(b+1,b+n+1),tot=unique(b+1,b+n+1)-b-1;
    for(int i=1;i<=n;++i)a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    for(int i=1;i<=B;++i)bl[i]=br[i-1]+1,br[i]=bl[i]+T-1;
    if(br[B]<n)++B,bl[B]=br[B-1]+1,br[B]=n;
    for(int i=1;i<=n;++i)be[i]=(i-1)/T+1;
    sort(q+1,q+m+1);
    memset(st,127,sizeof st);
    memset(ed,0,sizeof ed);
    for(int i=1,idx=1;i<=B;++i){
        memset(str,127,sizeof str);
        memset(edr,0,sizeof edr);
        memset(stl,127,sizeof stl);
        memset(edl,0,sizeof edl);
        R=br[i];
        tmp=0;
        while(be[q[idx].l]==i){
            L=br[i]+1;
            if(q[idx].r-q[idx].l<=T){
                ans[q[idx].id]=bf(q[idx].l,q[idx].r);
                ++idx;
                continue;
            }
            while(q[idx].r>R)++R,str[a[R]]=min(str[a[R]],R),edr[a[R]]=max(edr[a[R]],R),tmp=max(tmp,edr[a[R]]-str[a[R]]);
            cur=tmp;
            while(q[idx].l<L)--L,stl[a[L]]=min(stl[a[L]],L),edl[a[L]]=max(edl[a[L]],L),tmp=max(tmp,max(edl[a[L]],edr[a[L]])-min(stl[a[L]],str[a[L]]));
            ans[q[idx].id]=tmp;
            tmp=cur;
            while(L<=br[i])stl[a[L]]=2e9,edl[a[L]]=0,++L;
            ++idx;
        }
    }
    for(int i=1;i<=m;++i)write(ans[i]),putchar('\n');
    return 0;
}

回滚莫队的例题有点少，但是当比赛遇到普通莫队题然后删除操作怎么都想不出来时应该可以试试回滚偷 AC.

莫队＋根号分治/值域分块

莫队算法需要进行 $(N+M)\sqrt N$ 次增删操作和 $M$ 次答案记录操作，这就导致莫队特别适合出一些考察复杂度平衡的题。

P12598 参数要吉祥

别争论扶苏是男的还是女的了，扶苏是一个大语言模型。

由于是非人哉的东西所以可以想到莫队。莫队怎么维护呢？
首先删除和添加可以很容易地维护出现次数 c 和出现次数出现的次数 cc,但是怎么快速地把每个值不为 0 的 $c_i\times cc_{c_i}$ 抓出来呢？
暴力显然不现实。所以……

设分块的大小为 t, 我们先遍历整个数组，把值小于 t(就是 $\sqrt N$) 的 $c_i$ 的值存在一起（这种值最多有 $\sqrt N$个），另外存储存储满足 $c_i>t$ 的 i. 因为 c 代表的是一个数出现的次数，而出现次数大于 $\sqrt N$ 的数最多只能有 $\sqrt N$ 个，所以这部分数的数量最多也是 $\sqrt N$. 随后进入莫队环节，每次移动完区间后遍历这两个表更新答案，每个询问需要 $O(\sqrt N)$ 的时间复杂度，总共 $O(M\sqrt N)$, 总体复杂度依然是 $O((M+N)\sqrt N)$.
$Code:$

#include<bits/stdc++.h>
using namespace std;
int n,a[200005],m,t,c[200005],cc[200005],ans[200005],sp[200005],cnt;
struct q{
    int l,r,id;
}qry[200005];
bool cmp(q a,q b){
    if((a.l-1)/t!=(b.l-1)/t)return (a.l-1)/t<(b.l-1)/t;
    if(((a.l-1)/t)&1)return a.r<b.r;
    return a.r>b.r;
}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar('-'),x=-x;
    if(x>=10)write(x/10);
    putchar(x%10+'0');
}
int main(){
    n=read(),m=read(),t=sqrt(n);
    for(int i=1;i<=n;++i)a[i]=read(),c[a[i]]++;
    for(int i=1;i<=200000;++i)if(c[i]>t)sp[++cnt]=i;
    memset(c,0,sizeof(c));
    for(int i=1;i<=m;++i)qry[i]={read(),read(),i};
    sort(qry+1,qry+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=m;++i){
        int maxn=0;
        while(qry[i].l<L)--L,cc[c[a[L]]]--,c[a[L]]++,cc[c[a[L]]]++;
        while(R<qry[i].r)++R,cc[c[a[R]]]--,c[a[R]]++,cc[c[a[R]]]++;
        while(L<qry[i].l)cc[c[a[L]]]--,c[a[L]]--,cc[c[a[L]]]++,L++;
        while(qry[i].r<R)cc[c[a[R]]]--,c[a[R]]--,cc[c[a[R]]]++,R--;
        for(int j=1;j<=t;++j)maxn=max(maxn,j*cc[j]);
        for(int j=1;j<=cnt;++j)maxn=max(maxn,c[sp[j]]*cc[c[sp[j]]]);
        ans[qry[i].id]=maxn;
    }
    for(int i=1;i<=m;++i)write(ans[i]),putchar('\n');
    return 0;
}

P4867 Gty的妹子序列

自行读题。
一眼树套树、 K-D 树、 CDQ 分治，但是假设我们除了莫队什么都不会，因为题目的空间是丧心病狂的 32.00MB（说你呢，丧心病狂的 20MB ＋强制在线的简单题）.
有两个约束条件如何莫队？某个金名金钩的大佬发了篇 $O((N+M)\sqrt Nlog N)$ 的所谓题解，但是这题本意完全不是这样，并且这个做法也只有卡常才能过。
本题如果用 $O(1)$ 的时间复杂度单点增加或删除一个数、不大于 $O(\sqrt N)$ 的时间查询一个区间内的答案值就可以维持时间复杂度不变，我们只需要更新 cnt, 增加时如果以前没有这个数就按值域插入一个 1, 删除时如果现在没有这个数就设为 0, 最后移动完区间更新答案时求区间值。那么哪里有这样的 ds?

套值域分块模板即可。
$Code:$

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],m,t,cnt[100005],ans[1000005],be[100005],bl[1005],br[1005],num[1005];
struct q{
    int l,r,a,b,id;
}qry[1000005];
bool cmp(q a,q b){return ((a.l-1)/t^(b.l-1)/t)?(a.l-1)/t<(b.l-1)/t:(((a.l-1)/t)&1?a.r<b.r:a.r>b.r);}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
int main(){
    n=read(),m=read(),t=sqrt(n);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i)qry[i]={read(),read(),read(),read(),i};
    sort(qry+1,qry+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=n;++i)be[i]=(i-1)/t+1;
    for(int i=1;i<=be[n];++i)bl[i]=br[i-1]+1,br[i]=i*t;
    br[be[n]]=n;
    for(int i=1;i<=m;++i){
        while(qry[i].l<L)--L,cnt[a[L]]++,num[be[a[L]]]+=(cnt[a[L]]==1);
        while(R<qry[i].r)++R,cnt[a[R]]++,num[be[a[R]]]+=(cnt[a[R]]==1);
        while(L<qry[i].l)cnt[a[L]]--,num[be[a[L]]]-=(!cnt[a[L]]),++L;
        while(qry[i].r<R)cnt[a[R]]--,num[be[a[R]]]-=(!cnt[a[R]]),--R;
        for(int j=qry[i].a;j<=qry[i].b&&j<=br[be[qry[i].a]];++j)ans[qry[i].id]+=(bool)(cnt[j]);
        if(be[qry[i].a]^be[qry[i].b])for(int j=bl[be[qry[i].b]];j<=qry[i].b;++j)ans[qry[i].id]+=(bool)(cnt[j]);
        for(int j=be[qry[i].a]+1;j<be[qry[i].b];++j)ans[qry[i].id]+=num[j];
    }
    for(int i=1;i<=m;++i)write(ans[i]),putchar_unlocked('\n');
    return 0;
}

P4396 [AHOI2013] 作业

这题因为没有空间限制所以可以树套树、CDQ 分治、K-D 树。当然也可以从刚才那题的代码上改，新开一个分块存和就行了。2分钟过紫题我进国家集训队吧（其实系复制粘贴上一题然后改）
$Code:$

#include<bits/stdc++.h>
using namespace std;
int n,a[100005],m,t,cnt[100005],ans[100005],be[100005],bl[405],br[405],num[405],sum[405],tot[100005];
struct q{
    int l,r,a,b,id;
}qry[100005];
bool cmp(q a,q b){return ((a.l-1)/t^(b.l-1)/t)?(a.l-1)/t<(b.l-1)/t:(((a.l-1)/t)&1?a.r<b.r:a.r>b.r);}
int read(){
    int x=0,f=1,ch=getchar_unlocked();
    for(;!isdigit(ch);ch=getchar_unlocked())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar_unlocked())x=(x<<3)+(x<<1)+(ch^48);
    return x*f;
}
void write(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x>=10)write(x/10);
    putchar_unlocked(x%10+'0');
}
int main(){
    n=read(),m=read(),t=sqrt(n);
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=1;i<=m;++i)qry[i]={read(),read(),read(),read(),i};
    sort(qry+1,qry+m+1,cmp);
    int L=1,R=0;
    for(int i=1;i<=n;++i)be[i]=(i-1)/t+1;
    for(int i=1;i<=be[n];++i)bl[i]=br[i-1]+1,br[i]=i*t;
    br[be[n]]=n;
    for(int i=1;i<=m;++i){
        while(qry[i].l<L)--L,cnt[a[L]]++,num[be[a[L]]]+=(cnt[a[L]]==1),sum[be[a[L]]]++;
        while(R<qry[i].r)++R,cnt[a[R]]++,num[be[a[R]]]+=(cnt[a[R]]==1),sum[be[a[R]]]++;
        while(L<qry[i].l)cnt[a[L]]--,num[be[a[L]]]-=(!cnt[a[L]]),sum[be[a[L]]]--,++L;
        while(qry[i].r<R)cnt[a[R]]--,num[be[a[R]]]-=(!cnt[a[R]]),sum[be[a[R]]]--,--R;
        for(int j=qry[i].a;j<=qry[i].b&&j<=br[be[qry[i].a]];++j)ans[qry[i].id]+=(bool)(cnt[j]),tot[qry[i].id]+=cnt[j];
        if(be[qry[i].a]^be[qry[i].b])for(int j=bl[be[qry[i].b]];j<=qry[i].b;++j)ans[qry[i].id]+=(bool)(cnt[j]),tot[qry[i].id]+=cnt[j];
        for(int j=be[qry[i].a]+1;j<be[qry[i].b];++j)ans[qry[i].id]+=num[j],tot[qry[i].id]+=sum[j];
    }
    for(int i=1;i<=m;++i)write(tot[i]),putchar_unlocked(' '),write(ans[i]),putchar_unlocked('\n');
    return 0;
}

结语

莫队其实练的还是基础的一些 ds 和做题的思路，比如我就复习了值域分块，学了 bitset 维护莫队等。应该很久之后才会更新了，不过没有树上莫队和莫队二离的话看这一篇足够了。能不能点个赞大佬们QvQ