参考讲解
莫队算法将暴力与分块两个算法合二为一，可以称之为优雅的暴力
莫队是一个必须离线的算法
本质是通过改变查询的顺序来实现降低时间复杂度

样例：求一个区间中每个数出现次数的平方和（多次询问）

我们可以用暴力来做每次枚举L~R，这样的暴力注定不可，我们考虑先一个等级的暴力
一开始指针区间为0->0每一个查询，左指针left和右指针right不断更新
比如Left=2，Right=4,
而题目要求查询L=1，r=5
left就要向前移动一位，也就是left–，而left位置上（也就是L=1这个位置）出现的数的次数自然就要+1（因为原本不在区间内，而现在在了）
同理，right要向后移动一位

添加和删除代码 

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; }

指针移动代码 

for(long long i=1;i<=m;i++) {  long long 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; }

我们来分析一下时间复杂度，每一次询问移动两最大都会是O（N）
总复杂度为O（N*M）
貌似这样并不是很优化
接下来介绍莫队的核心
在本题中询问是多次的
我们按照询问给定的区间，然后对询问进行分块
比如九组询问：
2 3
1 4
4 5
1 6
7 9
8 9
5 8
6 8
数据范围为1~9，n=9，我们可以分成三块，
也就是1 ~ 3 , 4 ~ 6,7 ~ 9
我们以L为准来将询问划分到不同块
在每一个单独的块内，我们让R更小的排在前面
对上面的九组询问可得：
(2,3)/(1,4)/(1,6)
(4,5)/(5,8)/(6,8)
(7,9)/(8,9)

实现代码： 

bool cmp(node a,node b) {  return (a.r/block)==(b.r/block)?a.l<b.l:a.r<b.r; } /* //根据奇偶性排序 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; } */

此时时间复杂度为O（（N+M）*√N）
分析过程：
我将不大明白。。。所以直接引用参考题解

代码 

#include<bits/stdc++.h> 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; } /* //根据奇偶性排序 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; } */ 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; cin>>n>>m>>k; block=sqrt(n); for(long long i=1;i<=n;i++)cin>>c[i]; for(long long i=1;i<=m;i++) {  cin>>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 i=1;i<=m;i++) {  long long 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 i=1;i<=m;i++) printf("%lld\n",anss[i]); return 0; }

扩展

带修改莫队

参考博文
加入单点修改操作
将时间也加入询问，这样询问就变成了一个三元组（li,ri,ti）
从询问i移动到询问j的时间复杂度变成O（|li-ri|+|lj-rj|+|ti-tj|）
设m==n（即询问次数等于数的数量）
将序列分块，块的大小是n的三分之二次方，一共有n的三分之一次方个块
。将询问按左端点所在块的编号为第一关键字，右端点所在块的编号为第二关键字，时间为第三关键字排序。
（和之前比就是多个时间排序）
排序条件： 

int cmp(const node1 &a,const node1 &b) {  if (a.l/unit!=b.l/unit) return a.l/unit<b.l/unit; else if (a.r/unit!=b.r/unit) return a.r/unit<b.r/unit; else return a.x<b.x; }

主函数维护答案： 

void solve() {  int l=1,r=0,now=0; for (int i=1;i<=m;i++) {  while (r<q[i].r) update(r+1,1),r++; while (r>q[i].r) update(r,-1),r--; while (l>q[i].l) update(l-1,1),l--; while (l<q[i].l) update(l,-1),l++; while (now<q[i].x) change(now+1,1,l,r),now++; while (now>q[i].x) change(now,-1,l,r),now--; ans[q[i].id]=tot; } }

修改通过change实现： 

void change(int bh,int z,int l,int r) {  if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,-1); //删除从前的影响  swap(c[ch[bh].x],ch[bh].y); if (ch[bh].x>=l&&ch[bh].x<=r) update(ch[bh].x,1); //添加影响  }

树上莫队

如果例题改成：
给一颗n个点的树，点有点权，m次询问，每次询问xi到yi的路径上有多少个不同的点权
树上路径可以通过树的括号序转化成序列问题
用 first(x) 表示 x 在括号序里第一次出现的位置，则路径 (x,y)的信息就等于括号序上的区间 [first(x),first(y)] 的信息(设 first(x)<first(y) )，当 lca(x,y) 不是 x 也不是 y 时，还需要再加上 lca 的信息。