简要介绍：
莫队算法是先进行分块，然后按照分块来排序，然后对已知区间进行增减以达到所求区间，记录下答案，最后按照所询问的顺序进行输出答案。
如对于已知区间[l,r]要求[l-1，r],[l-2,r],[l-3,r],[l-4,r],则将已知区间向左移，同时进行add添加操作；
而对于要求[l,r+1],[l,r+2],[l,r+3],[l,r+4]则将已知区间向右移，同时进行add添加操作。
对于新区间，若已知区间范围比新区间小，则要在移动的同时，要把相应的答案加上(add操作)，而对于已知区间比新区间大的，则要在移动的同时，将相应的答案减去(del操作)。
主要模板：
莫队算法的区别主要在于add函数和del函数，对于不同的题目，所写的add函数和del函数不一样。其他主要架构基本一致。
主要架构为：
点击查看代码
int a[50005],pos[50005];
int ans=0;
int cnt[50005]={0};
int re[50005]={0};
struct Q
{
int l,r,id;
}q[50005];
bool cmp(Q &a,Q &b)
{
return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];
}
void solve()
{
int n,m,k;
cin>>n>>m>>k;
int siz=sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
pos[i]=i/siz;
}
for(int i=0;i<m;i++)
{
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q,q+m,cmp);
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(q[i].l<l)--l,add(l);
while(q[i].r>r)++r,add(r);
while(q[i].l>l)del(l),l++;
while(q[i].r<r)del(r),r--;
re[q[i].id]=ans;
}
for(int i=0;i<m;i++)
cout<<re[i]<<'\n';
}
洛谷P2709 小B的询问
点击查看代码
#include<bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
int a[50005],pos[50005];
int ans=0;
int cnt[50005]={0};
int re[50005]={0};
struct Q
{
int l,r,id;
}q[50005];
bool cmp(Q &a,Q &b)
{
return pos[a.l]==pos[b.l]?a.r<b.r:pos[a.l]<pos[b.l];
}
void add(int x)
{
cnt[a[x]]++;
ans+=(cnt[a[x]])*(cnt[a[x]])-(cnt[a[x]]-1)*(cnt[a[x]]-1);
}
void del(int x)
{
cnt[a[x]]--;
ans-=(cnt[a[x]]+1)*(cnt[a[x]]+1)-cnt[a[x]]*cnt[a[x]];
}
void solve()
{
int n,m,k;
cin>>n>>m>>k;
int siz=sqrt(n);
for(int i=1;i<=n;i++)
{
cin>>a[i];
pos[i]=i/siz;
}
for(int i=0;i<m;i++)
{
cin>>q[i].l>>q[i].r;
q[i].id=i;
}
sort(q,q+m,cmp);
int l=1,r=0;
for(int i=0;i<m;i++)
{
while(q[i].l<l)--l,add(l);
while(q[i].r>r)++r,add(r);
while(q[i].l>l)del(l),l++;
while(q[i].r<r)del(r),r--;
re[q[i].id]=ans;
}
for(int i=0;i<m;i++)
cout<<re[i]<<'\n';
}
signed main()
{
cin.tie(NULL);
cout.tie(nullptr);
ios_base::sync_with_stdio(false);
solve();
return 0;
}