莫队算法简介

莫队算法是一种用于高效处理离线区间查询问题的算法，由莫涛（Mo Tao）在2009年提出。其核心思想是通过对查询区间进行分块和排序，利用前一次查询的结果来减少计算量，从而将时间复杂度优化至接近线性。

莫队的基本实现步骤：

示范:洛谷P2709 小B的询问

1.定块长

将块长定为 $n\sqrt{n}$ 时间复杂度较为平均。
核心代码：

len=sqrt(n);

2.排序

将询问输入并进行排序。
核心代码：

bool cmp(node x,node y)
{if(x.l/len!=y.l/len)return x.l<y.lelse return x.r<y.r;
}

使用奇偶性优化。
就是如果 $l$ 在的块是奇数块，那么 $r$ 按照从小到大排序，否则按照大从小排序。

bool cmp(node x,node y)
{if(x.l/len!=y.l/len)return x.l<y.l;else{if(!((x.l/len)&1))//[0,len]是第一个块{return x.r<y.r;}else{return x.r>y.r;}}
}

3.移动区间，获得答案

核心代码：

for(int i=1,l=1,r=0;i<=m;i++)
{while(b[i].l<l)add(--l);//加上l-1while(b[i].r>r)add(++r);//加上r+1while(b[i].l>l)del(l++);//减去l,将l右移while(b[i].r<r)del(r--);//减去r,将r左移ans[b[i].id]=sum;//注意要用排序前的顺序
}

$a dd$ :

void add(int x)
{if(a[x]<=k)sum-=box[a[x]]*box[a[x]];box[a[x]]++;if(a[x]<=k)sum+=box[a[x]]*box[a[x]];
}

使用平方差公式优化：

void add
{box[a[x]]++;if(a[x]<=k)sum+=2*box[a[x]]-1;
}

$d e l$ :

void del(int x)
{if(a[x]<=k)sum-=box[a[x]]*box[a[x]];box[a[x]]--;if(a[x]<=k)sum+=box[a[x]]*box[a[x]];
}

使用平方差公式优化：

void del(int x)
{if(a[x]<=k)sum-=2*box[a[x]]-1;box[a[x]]--;
}

4.输出答案

for(int i=1;i<=m;i++)
{cout<<ans[i]<<'\n';
}

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 7,M=1e5 + 7;
int n,m,len,num,a[N],sum=0,box[N],k;
int ans[M];
struct node
{int l,r,id;
}b[M];
bool cmp(node x,node y)
{if(x.l/len!=y.l/len)return x.l<y.l;else{if(!((x.l/len)&1)){return x.r<y.r;}else{return x.r>y.r;}}
}
void add(int x)
{box[a[x]]++;if(a[x]<=k)sum+=2*box[a[x]]-1;
}
void del(int x)
{box[a[x]]--;if(a[x]<=k)sum-=2*box[a[x]]+1;
}
int main()
{cin>>n>>m>>k;len=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i].l>>b[i].r;b[i].id=i;}sort(b+1,b+m+1,cmp);for(int i=1,l=1,r=0;i<=m;i++){while(b[i].l<l)add(--l);while(b[i].r>r)add(++r);while(b[i].l>l)del(l++);while(b[i].r<r)del(r--);ans[b[i].id]=sum;}for(int i=1;i<=m;i++){cout<<ans[i]<<'\n';}return 0;
}