莫队也是一个比较厉害的算法。其本质也是暴力。
莫队在比赛中有时候还是很常见的。
本文是根据B站AgOH大佬讲解的莫队总结的。
莫队算法是一种可以解决大部分区间离线问题的离线算法。
所谓离线就是说他给的区间询问一下给完了，不是边询问边回答的动态的。
莫队的主要思想是分块。 时间复杂度O(n
n
\sqrt{n}
n? )
莫队算法的大致思想是这样的:
我们查询很多的区间,区间有时候是很相近的，那么我们就可以暴力的移动到相应的区间就行了。
大致思路就是先分块，分块主要是为了排序，然后排序。最后暴力的移动。
指针的移动有以下四种情况：
例题一：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
typedef long long int LL;
LL a[N],cnt[N],pos[N],ans[N];
LL n,m,k;
LL res;//保存当前状态的值
struct node{int l,r,id;}Node[N];
bool cmp(node a,node b)//排序
{
if(pos[a.l]==pos[b.l]) return a.r<b.r;
return pos[a.l]<pos[b.l];
}
void add(int x)
{
res-=cnt[a[x]]*cnt[a[x]];
cnt[a[x]]++;
res+=cnt[a[x]]*cnt[a[x]];
}
void sub(int x)
{
res-=cnt[a[x]]*cnt[a[x]];
cnt[a[x]]--;
res+=cnt[a[x]]*cnt[a[x]];
}
int main(void)
{
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i];
int len=sqrt(n);//分块
for(int i=1;i<=n;i++) pos[i]=i/len;//分块
for(int i=1;i<=m;i++)
{
int l,r; cin>>l>>r;
Node[i]={l,r,i};
}
sort(Node+1,Node+m+1,cmp);
int l=1,r=0;//这是一个闭的区间
//如果l=0,r=0 则此时是一个[0,0]区间，这样的话起始就有了一个区间
for(int i=1;i<=m;i++)
{
while(Node[i].l<l) add(--l);
while(Node[i].r>r) add(++r);
while(Node[i].l>l) sub(l++);
while(Node[i].r<r) sub(r--);
ans[Node[i].id]=res;
}
for(int i=1;i<=m;i++) cout<<ans[i]<<endl;
return 0;
}
例题二：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5*5+10;
typedef long long int LL;
LL n,m,ans;
LL va[N],pos[N],cnt[N],anw[N];
struct node
{
int l,r,id;
}Node[N];
bool cmp(node a,node b)
{
if(pos[a.l]!=pos[b.l]) return pos[a.l]<pos[b.l];
return a.r<b.r;
}
void add(int x)
{
ans-=cnt[va[x]]*cnt[va[x]]*va[x];
cnt[va[x]]+=1;
ans+=cnt[va[x]]*cnt[va[x]]*va[x];
}
void sub(int x)
{
ans-=cnt[va[x]]*cnt[va[x]]*va[x];
cnt[va[x]]-=1;
ans+=cnt[va[x]]*cnt[va[x]]*va[x];
}
int main(void)
{
cin>>n>>m;
for(int i=1;i<=n;i++) cin>>va[i];
int len=sqrt(n);//分块
for(int i=1;i<=n;i++) pos[i]=i/len;//分快
for(int i=1;i<=m;i++)
{
int l,r; cin>>l>>r;
Node[i]={l,r,i};
}
sort(Node+1,Node+m+1,cmp);
int l=1,r=0;
for(int i=1;i<=m;i++)
{
while(Node[i].l<l) add(--l);
while(Node[i].r>r) add(++r);
while(Node[i].l>l) sub(l++);
while(Node[i].r<r) sub(r--);
anw[Node[i].id]=ans;
}
for(int i=1;i<=m;i++) cout<<anw[i]<<'\n';
return 0;
}
总结： 你会发现莫队的题的基本框架几乎都是一样的，不一样的点主要就是add(),sub()函数的书写要根据实际情况写。
