莫队算法初探

log 2022.9.27 复活更新回滚莫队，删除了关于HH的项链的因为时代变迁的过时说法 ### 普通莫队 莫队算法（mo's algorithm）一般分为两类，一是莫队维护区间答案，二是维护区间内的数据结构。当然也有树上莫队，带修改莫队、二维莫队等等。这篇文章主要介绍的是普通莫队算法 我们考虑一个问题，给一个序列，m次询问，每次询问你区间$[l,r]$有多少种不同的颜色。$n,m\leq 100000$ ~~尽管可以用主席树做，但是我们假装不行~~ 先考虑暴力，对每次询问遍历一遍$[l,r]$，这样是$O(nm)$的， 换种方式暴力，定义ql和qr，表示区间$[ql,qr]$内有多少颜色，再定义cnt数组，$cnt_i$表示第i种颜色在区间$[ql,qr]$出现了多少次。 我们一个一个询问处理，对于询问$[l,r]$，我们挪动xl到l，xr到r 因为这个是莫队算法的基础，所以模拟一下这个过程：  我们的初始在这个状态，假设蓝色为1，红色为2，绿色为3 那么$cnt_1=3$,$cnt_2=3$,$cnt_3=1$，我们把qr向右挪一下  这样多了一个绿色，$cnt_3$加1 继续挪一下  多了一个红色，$cnt_2$加上1 此时我们发现，我们的右指针已经和询问的右端点重合了，接下来挪左指针  少了一个蓝色，$cnt_1$减去1 现在我们得出了答案为3，$cnt_1=2$,$cnt_2=4$,$cnt_3=2$ 提供这部分的代码： ```cpp inline void add(int x){ cnt[x]++; if(cnt[x]==1)ans++; } inline void del(int x){ cnt[x]--; if(cnt[x]==0)ans--; } //在获取答案时： while(l>q[i].l) add(a[--l]); while(r<q[i].r) add(a[++r]); while(l<q[i].l) del(a[l++]); while(r>q[i].r) del(a[r--]); ``` 我们发现，每次挪动都都是$O(1)$的，每次询问我们最多要挪动n次，所以时间复杂度还是$O(nm)$。 我们有没有办法来加速呢？ 这种暴力的耗时就耗在挪动次数上，我们要让他挪动的次数尽量少 肯定是有的，我们**将询问先储存下来**，再按照某种方法排序，让他减少挪动的次数，这样会变快一些 这种方法是**强行离线**,然后排序，所以这样的普通莫队不能资瓷修改 那么怎么排序呢？ 一种解决方式是优先按照左端点排序。 这种排序的方式，保证左端点只会向右挪，但是右端点每次最坏还是可以从最前面挪到最后面，从最后面挪到最前面，这样的复杂度还是$O(nm)$，是不行的 我们的排序是要使左右端点挪动的次数尽量少，所以这里就有一种排序方法： 将序列分成$\sqrt{n}$个长度为$\sqrt{n}$的块，若左端点在同一个块内，则按右端点排序（以左端点所在块为第一关键字，右端点为第二关键字） 注意，莫队的挪动操作要尽量快，若不是$O(1)$的，复杂度会原地爆炸 对于n与m同阶，一般可以设块长度为$\sqrt{n}$. 以下内容可以忽略，是我口胡的证明 >可以证明，这样的复杂度是$O(n\sqrt{n})$的，简略的提一下证明过程 >我们排序之后，每个块内均摊有根号$\sqrt{n}$个询问的l端点，显然这l个端点的右端点是有序的，最多一共会移动n次，所以对于一个块，复杂度是$O(n)$ >然后有根号n个块，所以总的复杂度是$O(n\sqrt{n})$ 但对于询问特别大的情况，$O(n\sqrt{n})$可能会超时，需要用其他的长度，我们来分析一下什么情况下均摊复杂度最优 我们设块长度为$S$，那么对于任意多个在同一块内的询问，挪动的距离就是$n$，一共$\frac{n}{S}$个块，移动的总次数就是$\frac{n^2}{S}$，移动可能跨越块，所以还要加上一个$mS$的复杂度，总复杂度为$O(\frac{n^2}{S}+mS)$，我们要让这个值尽量小，$S$取$\frac{n}{\sqrt{m}}$是最优的，此时复杂度为$O(\frac{n^2}{\frac{n}{\sqrt{m}}}+m(\frac{n}{\sqrt{m}}))=O(n\sqrt{m})$ >然而在随机情况下，发现块大小是$\frac{n}{\sqrt{m\times\frac{2}{3}}}$反而会快一些（因为询问的区间大小期望是 $n\times \frac{2}{3}$，因此每次挪动距离当成 $\frac{2}{3}n$ 处理） >还有一种卡常方法，按照奇偶性排序，我们正常的排序方式是这样的： ```cpp bool cmp(query a,query b){ return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r; } ``` >奇偶性排序是这样的： ```cpp bool cmp(node a,node b){ return pos[a.l]^pos[b.l]?pos[a.l]<pos[b.l]:pos[a.l]&1?a.r<b.r:a.r>b.r; } ``` >这样能快是因为指针移到右边后不用再跳回左边，而跳回左边后处理下一个块又要跳回右边，这样能减少一半操作，理论上能快一倍 **注意：分块时块的大小不是固定的，要根据题目具体分析，分析的过程如上面分析m极大时的复杂度** 刚刚那道数颜色其实是[ [SDOI2009]HH的项链](https://www.luogu.org/problemnew/show/P1972)，然而现在裸的莫队过不去了。 然而莫队吸口氧卡卡常还是能过的，不开O2会TLE 2 然而现在过不了力，有没有卡常大师再优化一手 ```cpp #include <bits/stdc++.h> using namespace std; int read() { char x; while((x = getchar()) > '9' || x < '0') ; int u = x - '0'; while((x = getchar()) <= '9' && x >= '0') u = (u << 3) + (u << 1) + x - '0'; return u; } int buf[105]; inline void write(int i) { int p = 0; if(i == 0) p++; else while(i) { buf[p++] = i % 10; i /= 10; } for(int j = p-1; j >= 0; j--) putchar('0' + buf[j]); } #define il inline #define re register int block,ans=0,cnt[1000001]; int n,m,a[500010],Ans[500010]; struct node { int l,r,id; }q[500010]; il bool cmp(node a,node b){ return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r); } il void add(int x){ if(!cnt[a[x]])ans++; cnt[a[x]]++; } il void del(int x){ cnt[a[x]]--; if(!cnt[a[x]])ans--; } int i; int main(){ n=read(); for(i=1;i<=n;++i)a[i]=read(); m=read(); block=n/sqrt(m*2/3); for(i=1;i<=m;++i){ q[i].l=read(); q[i].r=read(); q[i].id=i; } sort(q+1,q+m+1,cmp); int l=0,r=0; for(i=1;i<=m;++i){ int ql=q[i].l,qr=q[i].r; while(l<ql)del(l++); while(l>ql)add(--l); while(r<qr)add(++r); while(r>qr)del(r--); Ans[q[i].id]=ans; } for(i=1;i<=m;++i)write(Ans[i]),printf("\n"); return 0; } ``` 接下来是：[P2709 小B的询问](https://www.luogu.org/problemnew/show/P2709) 经典题，是裸的莫队 一句话题意：求一个区间中每个数出现次数的平方和 还是设$cnt_i$为i在当前区间出现的次数 如果$cnt_i$多了一个，那 > ans+=2*cnt[x]+1 如果$cnt_i$多了一个，那 > ans-=2*cnt[x]-1 没了。 ```cpp #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int maxn=50005; long long int c[maxn]; long long int sum[maxn]; struct node{ long long int l,r,num; }q[maxn]; long long anss[maxn]; long long int block; long long int ans=0; bool cmp(node a,node b){ return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r; } inline void del(int x){ sum[c[x]]--; ans-=2*sum[c[x]]+1; } inline void add(int x){ sum[c[x]]++; ans+=2*sum[c[x]]-1; } int main() { long long int n,m,k; scanf("%lld%lld%lld",&n,&m,&k); block=sqrt(n); for(long long int i=1;i<=n;i++){ scanf("%lld",&c[i]); } for(long long int i=1;i<=m;i++){ scanf("%lld%lld",&q[i].l,&q[i].r); q[i].num=i; } sort(q+1,q+1+m,cmp); int l=1,r=0; for(long long int i=1;i<=m;i++){ long long int ql=q[i].l,qr=q[i].r; while(l<ql){ del(l); l++; } while(l>ql){ l--; add(l); } while(r<qr){ r++; add(r); } while(r>qr){ del(r); r--; } anss[q[i].num]=ans; } for(long long int i=1;i<=m;i++){ printf("%lld\n",anss[i]); } return 0; } ``` ### 带修改莫队 普通莫队是不能带修改的 我们可以强行让它可以修改，就像DP一样，可以强行加上一维**时间维**,表示这次操作的时间。 即把询问$[l,r]$变成$[l,r,time]$ 那么我们的坐标也可以在时间维上移动，即$[l,r,time]$多了一维可以移动的方向，可以变成： - $[l-1,r,time]$ - $[l+1,r,time]$ - $[l,r-1,time]$ - $[l,r+1,time]$ - $[l,r,time-1]$ - $[l,r,time+1]$ 这样的转移也是$O(1)$的，但是我们排序又多了一个关键字，再搞搞就行了 可以用和普通莫队类似的方法排序转移，做到$O(n^{\frac{5}{3}})$ 这一次我们排序的方式是以$n^{\frac{2}{3}}$为一块，分成了$n^{\frac{1}{3}}$块，第一关键字是左端点所在块，第二关键字是右端点所在块，第三关键字是时间。 还是来证明一下时间复杂度（默认块大小为$n^\frac{2}{3}$）： - 左右端点所在块不变，时间在排序后单调向右移，这样的复杂度是$O(n)$ - 若左右端点所在块改变，时间一次最多会移动n个格子，时间复杂度$O(n)$ - 左端点所在块一共有$n^{\frac{1}{3}}$中，右端点也是$n^{\frac{1}{3}}$种，一共${n^{\frac{1}{3}}}\times{n^{\frac{1}{3}}}=n^{\frac{2}{3}}$种，每种乘上移动的复杂度$O(n)$，总复杂度$O(n^{\frac{5}{3}})$ ### 树上莫队 莫队只能处理线性问题，我们要把树强行压成一维的 我们可以将树的括号序跑下来，把括号序分块，在括号序上跑莫队 具体怎么做呢？ dfs一棵树，然后如果dfs到x点，就push_back(x),dfs完x点，就直接push_back(-x)，然后我们在挪动指针的时候 - 新加入的值是x ---> add(x) - 新加入的值是-x ---> del(x) - 新删除的值是x ---> del(x) - 新删除的值是-x ---> add(x) 这样的话，我们就把一棵树处理成了序列。 好像还有对树的连通块分块的方法，不过好像比较难我也不会( 例题是[[WC2013]糖果公园](https://www.luogu.org/problemnew/show/P4074),这题是带修改树上莫队 题意是给你一棵树,每个点有颜色,每次询问 $\sum_{c}val_c\sum_{i=1}^{cnt_c}w_i$ val表示该颜色的价值 cnt表示颜色出现的次数 w表示该颜色出现i次后的价值 先把树变成序列，然后每次添加/删除一个点，这个点的对答案的的贡献是可以在$O(1)$时间内获得的，即$val_c\times w_{cnt_{c+1}}$ 发现因为他会把起点的子树也扫了一遍，产生多余的贡献，怎么办呢？ 因为扫的过程中起点的子树里的点肯定会被扫两次，但贡献为0 所以可以开一个vis数组，每次扫到点x，就把$vis_x$异或上1 如果$vis_x=0$，那这个点的贡献就可以不计 所以可以用树上莫队来求 修改的话，加上一维时间维即可,变成带修改树上莫队 然后因为所包含的区间内可能没有LCA，对于没有的情况要将多余的贡献删除，然后就完事了 code： ```cpp #include<algorithm> #include<iostream> #include<cstdio> #include<cmath> #define DEBUG printf("line:%d func:%s\n",__LINE__,__FUNCTION__); using namespace std; const int maxn=200010; int f[maxn],g[maxn],id[maxn],head[maxn],cnt,last[maxn],dep[maxn],fa[maxn][22],v[maxn],w[maxn]; int block,index,n,m,q; int pos[maxn],col[maxn],app[maxn]; bool vis[maxn]; long long ans[maxn],cur; struct edge { int to,nxt; } e[maxn]; int cnt1=0,cnt2=0;//时间戳 struct query { int l,r,t,id; bool operator <(const query &b)const { return (pos[l]<pos[b.l])||(pos[l]==pos[b.l]&&pos[r]<pos[b.r])||(pos[l]==pos[b.l]&&pos[r]==pos[b.r]&&t<b.t); } } a[maxn],b[maxn]; inline void addedge(int x, int y) { e[++cnt]=(edge) { y,head[x] }; head[x]=cnt; } void dfs(int x) { id[f[x]=++index]=x; for(int i=head[x]; i; i=e[i].nxt) { if(e[i].to!=fa[x][0]) { fa[e[i].to][0]=x; dep[e[i].to]=dep[x]+1; dfs(e[i].to); } } id[g[x]=++index]=x;//括号序 } inline void swap(int &x,int &y) { int t; t=x; x=y; y=t; } inline int lca(int x,int y) { if(dep[x]<dep[y]) swap(x,y); if(dep[x]!=dep[y]) { int dis=dep[x]-dep[y]; for(int i=20; i>=0; i--) if(dis>=(1<<i)) dis-=1<<i,x=fa[x][i]; }//爬到同一高度 if(x==y) return x; for(int i=20; i>=0; i--) { if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i]; } return fa[x][0]; } inline void add(int x) { if(vis[x]) cur-=(long long )v[col[x]]*w[app[col[x]]--]; else cur+=(long long )v[col[x]]*w[++app[col[x]]]; vis[x]^=1; } inline void modify(int x,int t) { if(vis[x]) { add(x); col[x]=t; add(x); } else col[x]=t; }//在时间维上移动 int main() { scanf("%d%d%d",&n,&m,&q); for(int i=1; i<=m; i++) scanf("%d",&v[i]); for(int i=1; i<=n; i++) scanf("%d",&w[i]); for(int i=1; i<n; i++) { int x,y; scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } for(int i=1; i<=n; i++) { scanf("%d",&last[i]); col[i]=last[i]; } dfs(1); for(int j=1; j<=20; j++) for(int i=1; i<=n; i++) fa[i][j]=fa[fa[i][j-1]][j-1];//预处理祖先 int block=pow(index,2.0/3); for(int i=1; i<=index; i++) { pos[i]=(i-1)/block; } while(q--) { int opt,x,y; scanf("%d%d%d",&opt,&x,&y); if(opt==0) { b[++cnt2].l=x; b[cnt2].r=last[x]; last[x]=b[cnt2].t=y; } else { if(f[x]>f[y]) swap(x,y); a[++cnt1]=(query) { lca(x,y)==x?f[x]:g[x],f[y],cnt2,cnt1 }; } } sort(a+1,a+cnt1+1); int L,R,T;//指针坐标 L=R=0; T=1; for(int i=1; i<=cnt1; i++) { while(T<=a[i].t) { modify(b[T].l,b[T].t); T++; } while(T>a[i].t) { modify(b[T].l,b[T].r); T--; } while(L>a[i].l) { L--; add(id[L]); } while(L<a[i].l) { add(id[L]); L++; } while(R>a[i].r) { add(id[R]); R--; } while(R<a[i].r) { R++; add(id[R]); } int x=id[L],y=id[R]; int llca=lca(x,y); if(x!=llca&&y!=llca) { add(llca); ans[a[i].id]=cur; add(llca); } else ans[a[i].id]=cur; } for(int i=1; i<=cnt1; i++) { printf("%lld\n",ans[i]); } return 0; } ``` ### 回滚莫队！！ [例题](https://www.luogu.com.cn/problem/P5906): 给定一个序列，多次询问一段区间 $[l,r]$，求区间中**相同的数的最远间隔距离**. 当然本题普通莫队也是可以完成的，因为可以预处理每个数的相同前驱后继从而使删除操作变简单，这非常朴素. 考虑到朴素的莫队算法在处理删除操作时会有一些麻烦. 如本题中删除一个元素后更新下一个最远元素的操作肥肠困难. 而利用回滚莫队可以减少删除操作，让更多的操作是插入而非删除. 为了让操作只有插入没有删除，回滚莫队的排序方式是让询问从中心点向左右拓展，覆盖尽量多询问. 重复此操作直至所有询问被处理.