本文共 8044 字，大约阅读时间需要 26 分钟。

推荐几篇好的博客

以及这个

普通莫队

莫队算法是一种基于分块思想的离线算法

可以用来维护区间的答案和区间的数据结构

首先我们把长度为 \(n\) 的序列划分为 \(\sqrt{n}\) 个长度为 \(\sqrt{n}\) 的块并标号

然后把所有的询问离线下来，按照左端点所在的块的标号排序，如果标号相同，则按照右端点从小到大排序

询问的时候维护一个区间最左端的指针和一个区间最右端的指针

每次处理一个新的询问时，就分别移动左指针和右指针，使它们分别与新的询问的左右端点重合并记录答案

最后把存到数组里的答案输出即可

一般来说，\(n\) 和 \(m\) 可以看做是相等的，所以块长取 \(\sqrt{n}\) 最优

对于右端点来说，每一个块内的右端点是单调的，最多移动 \(n\) 的长度，一共有 \(\sqrt{n}\) 个块，所以复杂度为 \(n\sqrt{n}\)

对于左端点来说，每次最多移动一个块长，一共有 \(n\) 个左端点，所以复杂度为 \(n\sqrt{n}\)

再加上排序的 \(nlogn\) ,总的时间复杂度就是 \(n\sqrt{n}\)

但是当 \(n\) 和 \(m\) 不相等的时候，块长取 \(\frac{n}{\sqrt{m}}\) 是最优的，此时时间复杂度为 \(n\sqrt{m}\)

使用莫队算法的前提是没有强制在线，并且每次移动左指针和右指针改变的贡献能够快速计算

莫队算法在排序的时候还有一个奇偶性优化

如果左端点所属的联通块标号为奇数，按照右端点从小到大排序

否则按照右端点从大到小排序

这样排序大约要快 \(30\%\) 左右

代码

#include
   
    #include
    
     #include
     
      #include
      
       #define rg registerinline int read(){	rg int x=0,fh=1;	rg char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int maxn=1e6+5;int shuyu[maxn],a[maxn],n,m,k,cnt[maxn],num,blo,ans[maxn];struct asd{	int jla,jlb,id;}b[maxn];bool cmp(asd aa,asd bb){	if(shuyu[aa.jla]==shuyu[bb.jla]) return shuyu[aa.jla]&1?aa.jlb
       
        bb.jlb;	return aa.jla
        
         b[i].jla) xg(a[--l],1); while(r>b[i].jlb) xg(a[r--],-1); while(l
        
       
      
     
    
   

二维莫队

莫队也可以处理二维平面上的问题

但是排序的方式要改变一下

第一关键字：左上角的点的横坐标

第二关键字：左上角的点的纵坐标

第三关键字：右下角的点的横坐标

第四关键字：右下角的点的纵坐标

复杂度 \(n^2m^{\frac{3}{4}}\)

代码

#include
   
    #include
    
     #include
     
      #include
      
       #define rg registerinline int read(){	rg int x=0,fh=1;	rg char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int maxn=205,maxm=1e6+5;int n,m,q,a[maxn][maxn],shuyu[maxn],blo,ans[maxm],nans,sta[maxm],top,cnt[maxm];struct asd{	int ax,ay,bx,by,id;	asd(){}	asd(int aa,int bb,int cc,int dd,int ee){		ax=aa,ay=bb,bx=cc,by=dd,id=ee;	}}b[maxm];bool cmp(asd aa,asd bb){	if(shuyu[aa.ax]==shuyu[bb.ax]){		if(shuyu[aa.ay]==shuyu[bb.ay]){			if(shuyu[aa.bx]==shuyu[bb.bx]) return shuyu[aa.by]
       
        cc) std::swap(aa,cc);		if(bb>dd) std::swap(bb,dd);		b[i]=asd(aa,bb,cc,dd,i);	}	for(rg int i=1;i<=std::max(n,m);i++){		shuyu[i]=(i-1)/blo+1;	}	std::sort(b+1,b+1+q,cmp);	rg int nx=1,ny=1,mx=1,my=1;	nans=1;	cnt[a[1][1]]=1;	for(rg int i=1;i<=q;i++){		while(mx
        
         b[i].ax){ nx--; xgh(ny,my,nx,1); } while(ny>b[i].ay){ ny--; xgl(nx,mx,ny,1); } while(mx>b[i].bx){ xgh(ny,my,mx,-1); mx--; } while(my>b[i].by){ xgl(nx,mx,my,-1); my--; } while(nx
        
       
      
     
    
   

带修莫队

普通莫队加上了修改操作

那么排序的时候也要把修改的时间作为一个关键字排序

第一关键字：左端点属于的块

第二关键字：右端点属于的块

第三关键字：到当前查询的时候已经进行了多少次修改操作

当块长为 \(n^{\frac{2}{3}}\) 时，复杂度为 \(n^\frac{5}{3}\)

代码

#include
   
    #include
    
     #include
     
      #include
      
       #define rg registerinline int read(){	rg int x=0,fh=1;	rg char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int maxn=1e6+5,mod=1e6+3;int n,a[maxn],q,shuyu[maxn],cnt[maxn],mp[maxn],blo,ans[maxn],nans,sta[maxn],tp,cnt1,cnt2,jl[maxn];struct jie{	int l,r,id,tim;	jie(){}	jie(rg int aa,rg int bb,rg int cc,rg int dd){		l=aa,r=bb,id=cc,tim=dd;	}}b[maxn];bool cmp(jie aa,jie bb){	if(shuyu[aa.l]==shuyu[bb.l] && shuyu[aa.r]==shuyu[bb.r]){		return shuyu[aa.r]&1?aa.tim
       
        bb.tim;	} else if(shuyu[aa.l]==shuyu[bb.l]){		return shuyu[aa.l]&1?aa.r
        
         bb.r; } else { return shuyu[aa.l]
         
          =nl && c[ntim].wz<=nr){ sc(c[ntim].bef); ad(c[ntim].lat); } a[c[ntim].wz]=c[ntim].lat; } while(ntim>b[i].tim){ if(c[ntim].wz>=nl && c[ntim].wz<=nr){ ad(c[ntim].bef); sc(c[ntim].lat); } a[c[ntim].wz]=c[ntim].bef; ntim--; } while(nr
          
           b[i].l){ nl--; ad(a[nl]); } while(nr>b[i].r){ sc(a[nr]); nr--; } while(nl
          
         
        
       
      
     
    
   

回滚莫队

有些情况下，添加值很好做，但是删除值不好做

还有些情况下，删除值很好做，但是添加值不好做

此时普通的莫队无法做到移动左右指针的时候单次 \(O(1)\) 更新答案

就要用到另一种莫队：回滚莫队

回滚莫队又分为两种：只加不减的和只减不加的

只加不减

这道题要维护最大值

区间伸长的时候很好说，直接和当前的答案取个 \(max\) 即可

但是区间收缩的时候我们却无法快速地找到次大值，即使我们记录了次大值，有可能下一次又把次大值删除

所以我们要让莫队只能加入贡献，不能删除贡献

首先，我们把询问按照莫队的顺序排序

注意排序时不能使用奇偶性优化，而要按照右端点递增来排

排完序后，询问被分成了 \(\sqrt{n}\) 段

我们把每一段拿出来单独处理

设 \(r[i]\) 为第 \(i\) 段的右端点的下标，\(l[i]\)为第 \(i\) 段的左端点的下标

一开始，我们把左指针设为 \(r[i]+1\)

把右指针设为 \(r[i]\)

因为在每一段内右端点都是单调递增的，所以右端点一定只有加入的贡献

对于左端点，为了强制只能加入值

我们要在每次操作使用完成后把它回复成 \(r[i]+1\) 的状态 ，同时把之前左端点做的贡献清除

每一段统计完答案后，我们还要把右端点的贡献清清除

对于长度小于 \(\sqrt{n}\) 的块，暴力统计即可

代码

#include
   
    #include
    
     #include
     
      #include
      
       #define rg registerinline int read(){	rg int x=0,fh=1;	rg char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int maxn=1e5+5;int n,a[maxn],q,shuyu[maxn],cnt[maxn],blo,sta[maxn],tp,lmax[maxn],rmax[maxn],cnt2[maxn];long long ans[maxn],nans;struct jie{	int l,r,id;	jie(){}	jie(rg int aa,rg int bb,rg int cc){		l=aa,r=bb,id=cc;	}}b[maxn];bool cmp(jie aa,jie bb){	if(shuyu[aa.l]==shuyu[bb.l]){		return aa.r
       
        b[now].l) ad(a[--nl]);			ans[b[now].id]=nans;			nans=tmp;			while(nl<=rmax[i]) cnt[a[nl++]]--;			now++;		}	}	for(rg int i=1;i<=q;i++) printf("%lld\n",ans[i]);	return 0;}
       
      
     
    
   

只减不加

和只加不减的莫队同理

只要把右端点改成单调递减

把一开始的右指针置为 \(n\)，左指针置为 \(l[i]\) 即可

代码

#include
   
    #include
    
     #include
     
      #include
      
       #define rg registerinline int read(){	rg int x=0,fh=1;	rg char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int maxn=2e5+5;int n,a[maxn],q,shuyu[maxn],cnt[maxn],blo,lmax[maxn],rmax[maxn],cnt2[maxn],ans[maxn],nans,cnt3[maxn];struct jie{	int l,r,id;	jie(){}	jie(rg int aa,rg int bb,rg int cc){		l=aa,r=bb,id=cc;	}}b[maxn];bool cmp(jie aa,jie bb){	if(shuyu[aa.l]==shuyu[bb.l]){		return aa.r>bb.r;	} else {		return shuyu[aa.l]
       
        b[now].r){				sc(a[nr]);				nr--;			}			tmp=nans;			for(rg int j=nl;j
       
      
     
    
   

回滚莫队的复杂度和普通莫队是相同的

树上莫队

首先我们要把树变成一个序列

普通的 \(dfn\) 序可以处理子树上的问题

但是处理路径问题就要用到欧拉序

欧拉序的求法很简单，在刚 \(dfs\) 到一个点时加入序列，最后退出时也加入一遍

设 \(eul1[i]\) 表示访问到 \(i\) 时加入欧拉序的时间，\(eul2[i]\) 表示回溯经过 \(i\) 时加入欧拉序的时间

设 \(eul1[x]<eul1[y]\)

若 \(lca(x,y) = x\)，这时 \(x,y\)在一条链上，那么\(eul1[x]\) 到 \(eul1[y]\) 这段区间中，有的点出现了两次，有的点没有出现过，这些点都是对答案没有贡献的，我们只需要统计出现过 \(1\) 次的点就好

若\(lca(x,y) \neq x\)，此时 \(x,y\) 位于不同的子树内，我们只需要按照上面的方法统计 \(eul2[x]\) 到 \(eul1[y]\) 这段区间内的点，但是我们发现这里面的点不包括 \(lca\)，所以要把 \(lca\) 加上

代码

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #define rg registerinline int read(){	rg int x=0,fh=1;	rg char ch=getchar();	while(ch<'0' || ch>'9'){		if(ch=='-') fh=-1;		ch=getchar();	}	while(ch>='0' && ch<='9'){		x=(x<<1)+(x<<3)+(ch^48);		ch=getchar();	}	return x*fh;}const int maxn=1e5+5;int h[maxn],tot=1,n,q,blo,a[maxn],sta[maxn],tp2,eul1[maxn],eul2[maxn],dfn[maxn],dfnc;bool vis[maxn];struct asd{	int to,nxt;}b[maxn];void ad(rg int aa,rg int bb){	b[tot].to=bb;	b[tot].nxt=h[aa];	h[aa]=tot++;}int siz[maxn],dep[maxn],son[maxn],fa[maxn],rk[maxn],tp[maxn],nans,ans[maxn],cnt[maxn];void dfs1(rg int now,rg int lat){	dep[now]=dep[lat]+1;	eul1[now]=++dfnc;	rk[dfnc]=now;	siz[now]=1;	fa[now]=lat;	for(rg int i=h[now];i!=-1;i=b[i].nxt){		rg int u=b[i].to;		if(u==lat) continue;		dfs1(u,now);		siz[now]+=siz[u];		if(siz[u]>siz[son[now]]) son[now]=u;	}	eul2[now]=++dfnc;	rk[dfnc]=now;}void dfs2(rg int now,rg int top){	tp[now]=top;	if(son[now]) dfs2(son[now],top);	for(rg int i=h[now];i!=-1;i=b[i].nxt){		rg int u=b[i].to;		if(u==fa[now] || u==son[now]) continue;		dfs2(u,u);	}}int getlca(rg int xx,rg int yy){	while(tp[xx]!=tp[yy]){		if(dep[tp[xx]]
        
         bb.r; } else { return shuyu[aa.l]
         
          eul1[bb]) std::swap(aa,bb); cc=getlca(aa,bb); if(cc==aa){ c[i]=jie(eul1[aa],eul1[bb],i,0); } else { c[i]=jie(eul2[aa],eul1[bb],i,cc); } } std::sort(c+1,c+1+q,cmp); rg int nl=1,nr=0; for(rg int i=1;i<=q;i++){ while(nr
          
           c[i].l) xg(rk[--nl]); while(nr>c[i].r) xg(rk[nr--]); while(nl