基本莫队
概述
对于一个序列，如果有若干个区间询问,且对于每个询问【$l$，$r$】可以从【$lpm 1$，$r$】或【$l$，$rpm 1$】快速得出，那么我们可以使用莫队算法
莫队算法的大体思路是将询问存下来，每个询问由上一个询问推出来
如果我们对于每个每个询问都由上一个询问推出来，每个询问的复杂度可以达到O(n),整体复杂度可以是O(n^2)
但是如果我们使用莫队，复杂度可以达到O((n+m)sqrt(n))。
具体实现
我们先对序列分块，每块长度为sqrt(n)，然后以询问左端点所在的块为第一关键字，右端点的大小为第二关键字进行排序
然后每个区间由它的上一个区间推出来,虽然单次询问仍可能是O(n),
但是在块中每次询问l的移动最大为sqrt(n)，r的移动总和最大为n，块与块之间的移动最大为n
所以总复杂度为O((n+m)sqrt(n))
大致的代码如下
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 50005 int block[maxn],si; int ans[maxn]; struct Q{ int l,r,id; bool operator <(const Q& a)const{//排序时以左端点所在块为第一关键字，以右端点为第二关键字 if(block[l]!=block[a.l])return l<a.l; return r<a.r; } }a[maxn]; void revise(int l,int add){ } int main(){ int n,m;scanf("%d%d",&n,&m);si=sqrt(n);//si为每个块的大小 for(int i=1;i<=n;i++)block[i]=i/si;//算出每个块包含的区间 for(int i=0;i<m;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;//读入所有询问 sort(a,a+m);//按照询问左端点所在块和右端点排序 int l=1,r=0; for(int i=0;i<m;i++){//对于每个询问由上一个询问的区间转移到当前询问区间 while(l<a[i].l)revise(l++,-1); while(l>a[i].l)revise(--l,1); while(r<a[i].r)revise(++r,1); while(r>a[i].r)revise(r--,-1); ans[a[i].id]=？; } for(int i=0;i<m;i++)printf("%d ",ans[i]);//输出每个询问 return 0; }
例题
bzoj2038: [2009国家集训队]小Z的袜子(hose)
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 50005 #define LL long long int col[maxn],sum[maxn],block[maxn],si; LL squ[maxn],ans1[maxn],ans2[maxn],ans; struct Q{ int l,r,id; bool operator <(const Q& a)const{ if(block[l]!=block[a.l])return l<a.l; return r<a.r; } }a[maxn]; LL gcd(LL a,LL b){ return b?gcd(b,a%b):a; } void revise(int l,int add){ ans-=squ[sum[col[l]]];sum[col[l]]+=add;ans+=squ[sum[col[l]]]; } int main(){ int n,m;scanf("%d%d",&n,&m);si=sqrt(n); for(int i=1;i<=n;i++)scanf("%d",col+i),block[i]=i/si,squ[i]=1ll*i*i; for(int i=0;i<m;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].id=i;//读入所有询问 sort(a,a+m);//按照询问左端点所在块和右端点排序 int l=1,r=0; for(int i=0;i<m;i++){//对于每个询问由上一个询问的区间转移到当前询问区间 while(l<a[i].l)revise(l++,-1); while(l>a[i].l)revise(--l,1); while(r<a[i].r)revise(++r,1); while(r>a[i].r)revise(r--,-1); ans1[a[i].id]=ans-(a[i].r-a[i].l+1);ans2[a[i].id]=1ll*(a[i].r-a[i].l+1)*(a[i].r-a[i].l); //本来ans1=sigma(C[sum[col[i]]][2])=sigma(sum[col[i]]*(sum[col[i]]-1))的,但它=sigma(sum[col[i]]^2-sum[col[i]]) //ans=sigma(sum[col[i]]^2)且 sigma(sum[col[i]])=(a[i].r-a[i].l+1)所以ans1[a[i].id]=ans-(a[i].r-a[i].l+1) LL g=gcd(ans1[a[i].id],ans2[a[i].id]);ans1[a[i].id]/=g,ans2[a[i].id]/=g; } for(int i=0;i<m;i++)printf("%lld/%lld ",ans1[i],ans2[i]);//输出每个询问 return 0; }
带修改的莫队
如果询问之间还插入了修改，那么普通莫队的复杂度就会加上m*t(转移询问时还要加上修改，每两个询问之间的修改都可能是t)
于是我们要对普通的莫队做出一些修改
我们先对序列分块，每块长度为$n^{frac{2}{3}}$，然后以询问左端点所在的块为第一关键字，右端点所在的块为第二关键字，询问之前的修改次数为第三关键字进行排序
每次询问时不仅要移动l,r,也要移动t。
我们的排序将询问按左端点所在的块分成了$n^{frac{1}{3}}$个大块，每个大块又按右端点所在的块分成了$n^{frac{1}{3}}$个小块
总共有$n^{frac{2}{3}}$个小块，每个小块中t的移动总和最多为修改的总次数st，复杂度$O(n^{frac{2}{3}}t)$
每个大块中r的移动总和最多为n,复杂度$O(n^{frac{1}{3}}n)=O(n^{frac{4}{3}})$
每次l的移动最多是$n^{frac{2}{3}}$,复杂度$O(n^{frac{2}{3}}m)$
如果n,m,t是同一级别的,则总复杂度为$O(n^{frac{5}{3}})$
例题
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 10005 #define maxt 1005 int ans[maxn],col[maxn],block[maxn],si,st=-1,apper[maxn*100],ans1,l=1,r=0,now[maxn]; struct Q{//询问 int l,r,t,id; bool operator < (const Q &a)const{//排序的第一关键字为l所在块，第二关键字为r所在块，第三关键字为询问之前的修改次数t return (block[l]!=block[a.l])?l<a.l:(block[a.r]!=block[r])?r<a.r:t<a.t; } }a[maxn]; struct C{//修改 int pos,New,old; }op[maxt]; void change(int x,int y){ if(x>=l&&x<=r){ apper[col[x]]--; if(!apper[col[x]])ans1--; if(!apper[y])ans1++; apper[y]++; } col[x]=y; } void revise(int x,int add){ apper[col[x]]+=add; if(add>0)ans1+=apper[col[x]]==1; else ans1-=!apper[col[x]]; } int main(){ int n,m,size=0;scanf("%d%d",&n,&m);size=pow(n,2/3.0);//每块范围大小为n^(2/3) char s[2]; for(int i=1;i<=n;i++)scanf("%d",col+i),now[i]=col[i],block[i]=i/size;//读入原始序列并计算出每个块所包含的区间 for(int i=0;i<m;i++){ scanf("%s",s); if(s[0]=='Q'){ scanf("%d%d",&a[si].l,&a[si].r); a[si].t=st,a[si].id=si++; } else{ scanf("%d%d",&op[st].pos,&op[++st].New); op[st].old=now[op[st].pos]; now[op[st].pos]=op[st].New; } } sort(a,a+si); int t=-1; for(int i=0;i<si;i++){ while(t<a[i].t)change(op[t].pos,op[++t].New); while(t>a[i].t)change(op[t--].pos,op[t].old); while(l<a[i].l)revise(l++,-1); while(l>a[i].l)revise(--l,1); while(r<a[i].r)revise(++r,1); while(r>a[i].r)revise(r--,-1); ans[a[i].id]=ans1; } for(int i=0;i<si;i++)printf("%d ",ans[i]); return 0; }
树上莫队
将树进行分块，然后和普通莫队一样进行排序和修改。
分块方法为王室联邦分块，虽然王室联邦分块的每个不一定连通，
但是它的大小，数量都能保证，且同一个块内的元素的距离$le$块的大小
例题【WC2013】糖果公园-树上带修改莫队
#include<cstdio> #include<algorithm> #include<cmath> using namespace std; #define maxn 100005 #define LL long long int size,si,block[maxn],val[maxn],w[maxn],col[maxn],now[maxn]; struct Q{ int x,y,t,id; bool operator <(const Q &b)const{//排序的第一关键字为x所在块，第二关键字为y所在块，第三关键字为询问之前的修改次数t return (block[x]!=block[b.x])?block[x]<block[b.x]:(block[y]!=block[b.y]?block[y]<block[b.y]:t<b.t); } }q[maxn]; struct C{ int old,ne,x; }ch[maxn]; struct Edge{ int next,to; }edge[maxn*2]; int fi[maxn],se,fa[maxn][18],stack[maxn],t,depth[maxn]; inline void add_edge(int u,int v){ edge[++se].next=fi[u],fi[u]=se,edge[se].to=v, edge[++se].next=fi[v],fi[v]=se,edge[se].to=u; } void out(int s){ si++; while(t>s)block[stack[--t]]=si; } void dfs(int x,int s){ for(int i=1;i<18;i++)fa[x][i]=fa[fa[x][i-1]][i-1]; for(int i=fi[x];i;i=edge[i].next){ int v=edge[i].to; if(v==fa[x][0])continue; fa[v][0]=x,depth[v]=depth[x]+1,dfs(v,t); if(t-s>size)out(s);//如果当前子树栈中节点>=size,就自成一块 } stack[t++]=x; } void up(int &x,int d){ for(int i=17;i>=0;i--){ if(d&(1<<i))x=fa[x][i]; } } int lca(int u,int v){ if(depth[u]>depth[v])swap(u,v); up(v,depth[v]-depth[u]); for(int i=17;i>=0;i--){ if(fa[u][i]!=fa[v][i])u=fa[u][i],v=fa[v][i]; } if(u!=v)return fa[u][0]; return u; } bool vis[maxn]; LL ans,ans1[maxn];int num[maxn]; void update(int x){//更新x(原来在路径上就删掉，不在就加入) if(vis[x]){ vis[x]=0; ans-=1ll*w[num[col[x]]--]*val[col[x]]; } else{ vis[x]=1; ans+=1ll*w[++num[col[x]]]*val[col[x]]; } } void change(int x,int y){//将col[x]改成y while(x!=y){ if(depth[x]<depth[y])update(y),y=fa[y][0]; else update(x),x=fa[x][0]; } } void modify(int x,int y){//将x到y上的所有节点更新 if(!vis[x])col[x]=y; else{ update(x); col[x]=y; update(x); } } int main(){ int n,m,q1,u,v,op,t=0,cnt=0; scanf("%d%d%d",&n,&m,&q1);size=pow(n,0.6); for(int i=1;i<=m;i++)scanf("%d",val+i); for(int i=1;i<=n;i++)scanf("%d",w+i); for(int i=1;i<n;i++)scanf("%d%d",&u,&v),add_edge(u,v); for(int i=1;i<=n;i++)scanf("%d",col+i),now[i]=col[i]; depth[1]=1,dfs(1,0); while(t>0)block[stack[--t]]=si;//将最后剩下的节点加入最后一个块 for(int i=0;i<q1;i++){ scanf("%d%d%d",&op,&u,&v); if(op){ if(block[u]>block[v])swap(u,v);//小优化，将所有询问x的块都变的比y小以防止query(u,v),query(v,u)算两次的情况 q[cnt].x=u,q[cnt].y=v,q[cnt].t=t,q[cnt].id=cnt;cnt++; } else{ ch[t].x=u,ch[t].old=now[u],ch[t++].ne=v,now[u]=v; } } sort(q,q+cnt);u=v=1,t=0; for(int i=0;i<cnt;i++){ while(t<q[i].t)modify(ch[t].x,ch[t].ne),t++; while(t>q[i].t)t--,modify(ch[t].x,ch[t].old); change(u,q[i].x);change(v,q[i].y);u=q[i].x,v=q[i].y; int Lca=lca(q[i].x,q[i].y); update(Lca); ans1[q[i].id]=ans; update(Lca); } for(int i=0;i<cnt;i++){ printf("%lld ",ans1[i]); } return 0; }