#edu2002. 莫队-1

莫队-1

Update 2025.3.5 : Luogu博客需要科技才能访问，无奈只能搬运一下，这是之前的入门学习材料

好多同学问莫队二次离线，于是单独写一篇 莫队-2

莫队算法是一种可以解决大部分区间离线算法的离线算法，核心思想是分块 一般情况下时间复杂度为O(nn)O(n\sqrt{n}),超好写，是解决问题的很优雅的暴力方法。（当然毒瘤出题人也会卡莫队，比如强制在线，或复杂度TLETLE ）

假如有这样一道题：对于一个数列，每次给出一个询问L,RL,R ，求 [L,R][L,R] 的区间和。（强制使用莫队来做） 分析：

假设你现在已经知道区间 [2,5][2,5] 的区间和，求区间 [2,6][2,6] 区间和，怎么求？显然只需要在 [2,5][2,5] 的基础上加上第 66 项的贡献。求区间 [3,6][3,6] 的区间和，可以在区间 [2,5][2,5] 和的基础上，加上第 66 项的贡献，减去第 22 项的贡献，也就是当前区间的值是上一步区间左右端点一步一步挪动过去的。

对于当前区间 [L,R][L,R] ，可以分四种情况讨论挪动过程

  • 1.加上当前区间左边一格的贡献：Add(−−L)Add(--L)

  • 2.加上当前区间右边一格的贡献：Add(++R)Add(++R)

  • 3.减去当前区间左边一格的贡献：Sub(L++)Sub(L++)

  • 4.减去当前区间右边一格的贡献：Sub(R−−)Sub(R--)

注意：区间先扩大，再缩小，想一想为什么？（防止L>R）

当时这样做显然会超时，时间复杂度是 O(n∗m)O(n*m)

如果我们询问的顺序如下： [1,2],[n−1,n],[1,2],[n−1,n],[1,2],[n−1,n]...[1,2],[n-1,n],[1,2],[n-1,n],[1,2],[n-1,n]...

时间复杂度O(nm)O(nm)，显然TLE

但是如果修改一下询问顺序： [1,2],[1,2],[1,2],[n−1,n],[n−1,n],[n−1,n]...[1,2],[1,2],[1,2],[n-1,n],[n-1,n],[n-1,n]...

效率就会大大不同，也就是询问顺序会影响时间复杂度

莫涛大佬套了分块，巧妙的解决询问顺序，优化了时间复杂度。

排序规则： 对于一个询问[L,R][L,R]，对于LL按照其所在快排序，对于LL在同一块内的，按照RR的大小排序。

莫队主体框架是一样的，区别在于AddAdd和SubSub函数

主体框架

int a[N],pos[N],n,m,k,cnt[N];
ll res,ans[N];
struct node{
	int l,r,k;
}q[N];
cin>>n>>m>>k;
int len=sqrt(n);
for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		pos[i]=i/len;
	}
for(int i=1;i<=m;i++)cin>>q[i].l>>q[i].r,q[i].k=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)add(--l);
		while(q[i].r>r)add(++r);
		while(q[i].l>l)sub(l++);
		while(q[i].r<r)sub(r--);
		ans[q[i].k]=res;
	}
for(int i=1;i<=m;i++)
	cout<<ans[i]<<endl;

自定义排序

bool cmp(node x,node y)
{
	return pos[x.l]==pos[y.l]?(x.r<y.r):(pos[x.l]<pos[y.l]);
}

也可以在定义排序里面计算左端点所在的块，这样主函数就不用再计算所在的块。 自定义函数修改如下：

bool cmp(node a,node b)
{
	return (a.l/len==b.l/len)?(a.r<b.r):(a.l<b.l);
}

复杂度分析

序列长度为nn,询问次数为mm，设块长为LL，分成n/Ln/L块。

对于RR,块内按照从小到大排序，移动总次数最坏情况下是O(n)O(n)（从最小移动到最大），总共n/Ln/L块，那复杂度就为O(n2/L)O(n^2/L)。

对于LL,块内移动复杂度为O(n2/L)O(n^2/L).块间移动，从第ii块移动到第i+1i+1块，移动长度为块长O(L)O(L)，mm次询问，最坏情况每一次询问左端点落在一个块内，那么时间复杂度为O(Lm)O(Lm)。

那么总时间复杂度为：

O(n2/L+n2/L+Lm)O(n^2/L+n^2/L+Lm)，根据不等式，当n2/L=Lmn^2/L=Lm时不等式区最小值，此时L=n/mL=n/\sqrt{m}，时间复杂度为O(nm)O(n\sqrt{m})。

当nn与mm数量级相同，L=nL=\sqrt{n},时间复杂度为O(nn)O(n\sqrt{n})

其他情况，块长应取L=n/mL=n/\sqrt{m}

例题1：SP3267 DQUERY - D-query

分析： 本题是弱化版HH的项链,HH的项链莫队会超时，可以利用这个题目学习莫队入门。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int n,m,a[N];
struct node{
	int l,r,id;
}q[N];
int len,num,qans[N];
//len为块的长度 num为块个数
//ans[i] 为第i个询问的答案 
int ans,cnt[N]; //颜色计数数组 
bool cmp(node a,node b)
{
	//return  (a.l/len)^(b.l/len)?a.l<b.l:(((a.l/len)&1)?a.r<b.r:a.r>b.r);;
	return (a.l/len==b.l/len)?(a.r<b.r):(a.l<b.l);
} 
void add(int x)
{
	cnt[a[x]]++;
	if(cnt[a[x]]==1)ans++; //新加入一种颜色 
	
}
void del(int x)    //减掉一种颜色 
{
	cnt[a[x]]--;
	if(cnt[a[x]]==0)ans--;	
} 
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",a+i);
		
	scanf("%d",&m);
	
	len=sqrt(n);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;	
	 } 
	sort(q+1,q+m+1,cmp);
	int l=0,r=0;
	for(int i=1;i<=m;i++)
	{
		int ql=q[i].l,qr=q[i].r;
		while(l>ql)add(--l);
		while(r<qr)add(++r);
		while(l<ql)del(l++);		
		while(r>qr)del(r--);
		qans[q[i].id]=ans; 
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",qans[i]);	
	return 0;
}

例2：P2709 小B的询问

莫队的经典板子题，增加或减掉一个点，那么就减掉之前的贡献，加上新贡献。

void add(int x)
{
	cnt[a[x]]++;
	res+=(cnt[a[x]]*cnt[a[x]])-(cnt[a[x]]-1)*(cnt[a[x]]-1);
}
void sub(int x)
{
	cnt[a[x]]--;
	res-=(cnt[a[x]]+1)*(cnt[a[x]]+1)-(cnt[a[x]]*cnt[a[x]]);
}

完整参考代码：点击

SP10707 COT2 - Count on a tree II

树上莫队，利用欧拉序，将树上路径问题改变为区间上的问题。

#include<bits/stdc++.h>
using namespace std;
const int N=4e4+10,M=1e5+10;
int head[N],tot;
struct node{
	int to,next;
}edge[N<<1]; 
struct nodeq
{
	int l,r,lca;
	int id;
}q[M];
int dep[N],ola[N<<1],fa[N][30],first[N],last[N],cnt;
//ola[] 欧拉序 
//first[i] last[i] 节点i在欧拉序开始\结束位置 cnt 欧拉序计数编号 
int len,ans,qans[M],col[N];
//len为分块的大小
//ans统计颜色数 qans[i] 第i次询问的答案 
int n,m,a[N],b[N];
//a[i]节点i的颜色编号 b数组用于离散化 
void add(int from,int to)
{
	edge[++tot].to=to;
	edge[tot].next=head[from];
	head[from]=tot;
} 
void dfs(int x,int father)
 {
 	ola[++cnt]=x; 
 	first[x]=cnt;
	for(int i=head[x];i;i=edge[i].next)
	{
		int y=edge[i].to;
		if(y==father)continue;
		dep[y]=dep[x]+1;
		fa[y][0]=x;
		for(int i=1;(1<<i)<=dep[y];++i)
			fa[y][i]=fa[fa[y][i-1]][i-1];
		dfs(y,x);
	}  
	ola[++cnt]=x;
	last[x]=cnt;
}
int getlca(int u,int v)
{
	if(dep[u]>dep[v])swap(u,v);
	for(int i=20;i>=0;i--)
		if(dep[fa[v][i]]>=dep[u])v=fa[v][i];
	if(u==v)return u;
	for(int i=20;i>=0;i--)
		if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i];
	return fa[u][0];
}
void add(int x)
{
	if(col[x]==0)ans++;
	col[x]++;
	
}
void del(int x)
{
	if(col[x]==1)ans--;
	col[x]--;
	
}
bool vis[N];   //vis[i]表示位置i是否在统计区间内 1 表示在统计区间内 0 表示不在统计区间内 
void work(int pos) {
	if(vis[pos])del(a[pos]);
	else add(a[pos]);
	vis[pos]^=1;
}

int cmp(nodeq a,nodeq b)
{
	return (a.l/len ==b.l/len)?(a.r<b.r):(a.l<b.l);
 } 

int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d",a+i),b[i]=a[i];
	
	//离散化
	sort(b+1,b+n+1);
	for(int i=1;i<=n;i++)
		a[i]=lower_bound(b+1,b+n+1,a[i])-b;   
		 
	for(int i=1;i<n;i++)
	{
		int u,v;scanf("%d%d",&u,&v);
		add(u,v);
		add(v,u); 
	} 
	dep[1]=1;
	dfs(1,-1);
		
	for(int i=1;i<=m;i++)
	{
		int x,y,lca;
		scanf("%d%d",&x,&y);
		lca=getlca(x,y);
		if(first[x]>first[y])swap(x,y);
		if(x==lca){
			q[i].l=first[x];
			q[i].r=first[y];
		}
		else
		{
			q[i].l=last[x];
			q[i].r=first[y];
			q[i].lca=lca;
		}
		q[i].id=i;
	}
	len=sqrt(n); //块的大小 
	sort(q+1,q+m+1,cmp);
	
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		int ql=q[i].l,qr=q[i].r,lca=q[i].lca;
		while(l>ql)work(ola[--l]);
		while(r<qr)work(ola[++r]);
		while(l<ql)work(ola[l++]);		
		while(r>qr)work(ola[r--]);
						
		if(lca)add(a[lca]);
		qans[q[i].id]=ans;
		if(lca)del(a[lca]);
	}
	for(int i=1;i<=m;i++)
		printf("%d\n",qans[i]);
	return 0;
}

学习完毕

{{ select(1) }}

  • YES
  • NO
  1. 关于
  2. 联系我们
  3. Language
  4. 兼容模式
  5. 主题
  3. Worker 0 in 59ms
  4. Powered by Hydro v4.13.3 Modified by byx QQ465039728
  5. 陕ICP备2023000766号