莫队算法
主要基于分块的思想
用结构体记录询问的左右端点及询问编号 （这是一个离线算法）
通过排序优化指针扫描顺序优化时间复杂度 。
1.普通莫队
例题:SP3267 DQUERY – D-query.
一、分块 ：
n=read);ll k=sqrtn);//块的大小允许调整forint i=1;i<=n;i++){a[i]=read);kuai[i]=i-1)/k+1;}
优化1：快读（&快输）
二、 排序（以左端点所在块编号递增）
inline bool cmp1question &x,question &y){return kuai[x.l]^kuai[y.l])?x.l<y.l:kuai[x.l]&1)?x.r<y.r:x.r>y.r;
}//cmp函数
优化2：奇偶排序 ——对于左端点在同一奇数块的询问区间，右端点升序排列，反之右端点降序。
然后在主函数中cmp函数sort即可 。该优化只可在普通莫队中使用）
三、莫队：
void deal){ll l=1,r=0;ll ans=0;forint i=1;i<=m;i++){//对于排序后的每个询问whilel>q[i].l) ans+=!cou[a[--l]]++;//cou数组记录出现次数/*{l--;cou[a[l]]++;ifcou[a[l]]==1) ans++;}*/whiler<q[i].r) ans+=!cou[a[++r]]++;/*{r++;cou[a[r]]++;ifcou[a[r]]==1) ans++;}*/whilel<q[i].l) ans-=!--cou[a[l++]];/*{cou[a[l]]--;ifcou[a[l]]==0) ans--;l++; }*/whiler>q[i].r) ans-=!--cou[a[r--]];/*{cou[a[r]]--;ifcou[a[r]]==0) ans--;r--; }*/q[i].ans=ans;}return;
}
去掉注释后代码并不长
优化3：移动指针时的常数压缩。
以上3种优化分别可缩短每个点的运行时间近200ms ，是莫队区分于On2)算法的重要手段。
例题代码
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll MAXN = 1234567 ;
ll a[MAXN];
ll n,m;
ll kuai[MAXN];
inline ll read){ll s=0,w=1;char ch=getchar);whilech<'0'||ch>'9'){ifch=='-')w=-1;ch=getchar);}whilech>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar);return s*w;
}
char integ[50];
inline void qoutint x){ifx<0)putchar'-'),x=-x;int len=0;do{integ[len++]=x%10+'0';x/=10;}whilex);whilelen--){putcharinteg[len]);}
}
struct question{ll l,r,num_;ll ans;
}q[MAXN];
int cou[MAXN];
inline bool cmp1question &x,question &y){return kuai[x.l]^kuai[y.l])?x.l<y.l:kuai[x.l]&1)?x.r<y.r:x.r>y.r;
}
inline bool cmpquestion &x,question &y){return x.num_<y.num_;
}
inline void deal){ll l=1,r=0;ll ans=0;forint i=1;i<=m;i++){whilel>q[i].l) ans+=!cou[a[--l]]++;whiler<q[i].r) ans+=!cou[a[++r]]++;whilel<q[i].l) ans-=!--cou[a[l++]];whiler>q[i].r) ans-=!--cou[a[r--]];/*{cou[a[r]]--;ifcou[a[r]]==0) ans--;r--;}*/q[i].ans=ans;}return;
}
int main){n=read);ll k=sqrtn);forint i=1;i<=n;i++){a[i]=read);kuai[i]=i-1)/k+1;}m=read);forint i=1;i<=m;i++){q[i].l=read);q[i].r=read);q[i].num_=i;}sortq+1,q+m+1,cmp1);deal);sortq+1,q+m+1,cmp);//还原成询问的顺序forint i=1;i<=m;i++){qoutq[i].ans);printf"\n");}return 0;
}//代码很好写
2.带修莫队
例题：Luogu P1903 [国家集训队]数颜色 / 维护队列.
做法：
1.将询问编号，假设编号为t,那么t就是最近（之前）的一个修改操作出现的编号（即第几个修改操作，类似于时间戳）。
2.在主算法中定义一个当前时间戳，比如 t 。对于每个查询操作，如果当前t大了，说明已进行的修改操作比要求的多，就把多改的改回来，反之往后修改。仅当前区间和查询区间时间戳、左右端点均相同时，才记录本次查询的答案。（建议通过代码理解）
其实就是在移动l,r的基础上多了一个t,且都只能左右移。
带修莫队的排序函数：（多了个关键字t）
排序函数：
inline int cmpquery a,query b){return kuai[a.l]^kuai[b.l])?kuai[a.l]<kuai[b.l]:kuai[a.r]^kuai[b.r])?kuai[a.r]<kuai[b.r]:a.ti<b.ti;
}
代码
//自己写（chao ti jie）
3.树上莫队
例题：SP10707 COT2 – Count on a tree II.
做法：
1.欧拉序（刚dfs到一个点时加入序列，退出时也加入）+lca函数
2.莫队
莫队做法：
1.设每个点的编号u在欧拉序中首次出现位置first[u]，最后出现位置为last[u]。
2.对于询问x→y，使first[x]<=first[y]（不满足就swap），这样处理后，若x和y有一个节点是另一个的祖先，那么lcax,y)=x。
3.若lcax,y)=x，则使用[first[x],first[y]]区间，反之使用[last[x],first[y]]区间（first[x],last[x])不会在路径上，因为出现了两次），但这个区间内不含lcax,y)，查询的时候要加上lca。
例题代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 256789;
inline int read){int w=1,s=0;char ch=getchar);whilech<'0'||ch>'9'){ifch=='-') w=-1;ch=getchar);}whilech>='0'&&ch<='9'){s=s<<3)+s<<1)+ch^48);ch=getchar);}return w*s;
}
int he[MAXN*2],ne[MAXN*2],to[MAXN*2],tot;void addint x,int y){tot++;ne[tot]=he[x];he[x]=tot;to[tot]=y;tot++;ne[tot]=he[y];he[y]=tot;to[tot]=x;
}
struct query{int l,r,lca,c1,c2,id;
}q[MAXN];
int ord[MAXN*2],val[MAXN],vis[MAXN],kuai[MAXN],ans[MAXN],now,cnt[MAXN],n,m,L[MAXN],R[MAXN],inp[MAXN];
int cmpquery x,query y){return kuai[x.l]^kuai[y.l]) ?kuai[x.l]<kuai[y.l]):kuai[x.l]&1)?x.r<y.r:x.r>y.r);
}
void workint pos){vis[pos]?now-=!--cnt[val[pos]]:now+=!cnt[val[pos]]++;vis[pos]^=1;//体会该标记的妙处（雾 ， 在树上带修莫队中也要用，【只有出现一次的才被统计】
}
int ncnt,depth[MAXN],f[MAXN][40];
int first[MAXN],last[MAXN];
void dfsint u,int fa){f[u][0]=fa;forint i=1;i<=30;i++)f[u][i]=f[f[u][i-1]][i-1];ord[++ncnt] = u;first[u]=ncnt;depth[u]=depth[fa]+1;f[u][0]=fa;forint e=he[u];e;e=ne[e]){int v=to[e];ifv==fa)continue;dfsv,u);} ord[++ncnt]=u;last[u] = ncnt;
}//欧拉序和倍增lca同时处理
int lcaint x,int y){ifdepth[x]<depth[y]) swapx,y);forint i=30;i>=0;i--){ifdepth[f[x][i]]>=depth[y]) x=f[x][i];ifx==y) return x;}forint i=30;i>=0;i--){iff[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];}return f[x][0];
}int main){n=read);m=read);forint i=1;i<=n;i++) inp[i]=val[i]=read);sortinp+1,inp+n+1);int tot=uniqueinp+1,inp+n+1)-inp-1;forint i=1;i<=n;i++){val[i]=lower_boundinp+1,inp+tot+1,val[i])-inp;}//离散化forint i=1;i<n;i++) addread),read));int x,y,c,cc;depth[1]=1;dfs1,0);int t=sqrtncnt);forint i=1;i<=t;i++) L[i]= i-1)*t,R[i]=i*t-1;ifR[t]<ncnt) t++,L[t]=R[t-1]+1,R[t]=ncnt;forint i=1;i<=t;i++) forint j=L[i];j<=R[i];j++)kuai[j]=i;forint i=1;i<=m;i++){x=read),y=read);int lc=lcax,y);iffirst[x]>first[y]) swapx,y);ifx==lc){q[i].l=first[x];q[i].r=first[y];}else{q[i].l=last[x];q[i].r=first[y];q[i].lca=lc;}q[i].id=i;}sortq+1,q+m+1,cmp);int l=1,r=0;forint i=1;i<=m;i++){int ln=q[i].l,rn=q[i].r;whilel<ln) workord[l++]);whilel>ln) workord[--l]);whiler<rn) workord[++r]);whiler>rn) workord[r--]);ifq[i].lca) workq[i].lca);ans[q[i].id]=now;ifq[i].lca) workq[i].lca);}forint i=1;i<=m;i++){printf"%d\n",ans[i]);}return 0;
}
树上带修莫队例题 糖果公园.（很简单 )
练习题
Gty的二逼妹子序列.
小Z的袜子.