莫队算法
传说中能解决一切区间问题的算法
这个算法是由之前的国家队队长莫涛巨神(%%%)发明的，所以尊称莫队算法。
- 目前的题型概括为三种：普通莫队，树形莫队以及带修莫队。这里讲普通莫队算法
-
题目
P2709 小B的询问 -
题目描述
小B有一个序列，包含N个1~K之间的整数。他一共有M个询问，每个询问给定一个区间[L..R]，求\sum{C_i^2}的值,其中i的值从1到K，其中C_i表示数字i在[L..R]中的重复次数。小B请你帮助他回答询问。
分析&举个栗子
掌握一个思想基础：两个询问之间的状态跳转。如图，当前完成的询问的区间为[a,b],下一个询问的区间为[p,q],现在保存[a,b]区间内的每个颜色出现次数的cnt[]数组已经准备好，[a,b]区间询问的答案ans1已经准备好，怎样用这些条件求出[p,q]区间询问的ans2？
考虑指针向左或向右移动一个单位，我们要付出多大的代价才能维护ans?即使得ans保存的是当前[l,r]的信息。我们对图中l,r的向右移动一格进行分析：
如图l指针向右移动一个单位，所造成的后果就是：我们损失了一个绿色方块。那么怎样维护：cnt[绿色]-1。那ans如何维护？
(C_i+1)^2=C_i^2+(2\times C_i+1) \\
(C_i-1)^2=C_i^2-(2\times C_i-1)
不难看出，我们可以直接向给以前ans +2*c[i]+1(或 -(2*c[i]-1))。同理，下面的r指针移动，将是差不多的。
如图r指针的移动带来的后果是，我们多了一个橙色方块。所以操作和上文相似，只不过是cnt[橙色]++。
回归正题地，我们发现，知道一个区间的信息，要求出旁边区间的信息（旁边区间指的是当前区间的一个指针通过加一减一得到的区间），竟只需要O(1)的时间。
但是就算是这样，到这里为止的话莫队算法依旧无法焕发其光彩，原因是：如果我们以读入的顺序来枚举每个询问，每个询问到下一个询问时都用上述方法维护信息，那么在你脑海中会浮现出l,r跳来跳去的疯狂景象，疯狂之处在于最坏情况下时间复杂度为：O(n^2)——如果要这样玩，那不如写一个暴力程序。
“莫队算法巧妙地将询问离线排序，使得其复杂度无比美妙……”
在一般做题时我们时常遇到使用排序来优化枚举时间消耗的例子。莫队的优化基于分块思想：对于两个询问，若在其l在同块，那么将其r作为排序关键字，若l不在同块，就将l作为关键字排序（这就是双关键字）。若使用pos[i]数组表示i所属的块是谁。排序如：
bool operator <(const Mo &rhs) const
{
if(pos==rhs.pos)return r<rhs.r;
else return l<rhs.l;
}
值得强调的是，我们是在对询问进行操作。
时间复杂度分析（分类讨论思想）：
首先，枚举m个答案，就一个m了。设分块大小为unit。
分类讨论：
1. l的移动：若下一个询问与当前询问的l所在的块不同，那么只需要经过最多2*unit步可以使得l成功到达目标.复杂度为：O(m*unit)
2. r的移动：r只有在pos[l]相同时才会有序（其余时候还是疯狂地乱跳，你知道，一提到乱跳，那么每一次最坏就要跳n次！），pos[l]什么时候相同？在同一块里面l就pos[]相同。对于每一个块，排序执行了第二关键字：r。所以这里面的r是单调递增的，所以枚举完一个块，r最多移动n次。总共有n/unit个块:复杂度为：O(n*n/unit)
总结：O(n*unit+n^2/unit)（n,m同级，就统一使用n）
根据基本不等式得：当n为 sqrt(n) 时，得到莫队算法的最优复杂度： O(n\sqrt n)
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 50010
#define LL long long
using namespace std;
int n,m,k,unit;
struct Mo
{
int l;
int r;
int id;
int pos;
bool operator <(const Mo &rhs) const
{
if(pos==rhs.pos)return r<rhs.r;
else return l<rhs.l;
}
}a[N];
int b[N],cnt[N];
LL Ans[N];
int main()
{
scanf("%d%d%d",&n,&m,&k);
unit=sqrt(n+1);
for(int i=1;i<=n;i++)scanf("%d",&b[i]);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a[i].l,&a[i].r);
a[i].id=i;
a[i].pos=a[i].l/unit;
}
sort(a+1,a+1+m);
int l=1,r=0;
LL ans=0;
for(int i=1;i<=m;i++)
{
while(l>a[i].l){l--;ans+=(cnt[b[l]]*2+1);cnt[b[l]]++;}
while(r<a[i].r){r++;ans+=(cnt[b[r]]*2+1);cnt[b[r]]++;}
while(l<a[i].l){ans-=(cnt[b[l]]*2-1);cnt[b[l]]--;l++;}
while(r>a[i].r){ans-=(cnt[b[r]]*2-1);cnt[b[r]]--;r--;}
Ans[a[i].id]=ans;
}
for(int i=1;i<=m;i++)
printf("%lld\n",Ans[i]);
return 0;
}
注： 部分引自大米饼的博客
树上莫队
树上莫队是莫队算法的拓展，思想依然差不多，下面我介绍一种树上莫队的做法。
首先弄出树的括号序。（对树做一次深搜，第一次进入某节点时，将此节点编号加入序列，从某节点退出时，将此节点编号第二次加入序列）
如图，有一棵树，以及它的括号序：
然后记录一个数在括号序中第一次出现和最后一次出现的位置。
如果要询问j到k之间路径的信息，需进行分类讨论：
（以下均遵循此原则，出现两次的数字不算入所求信息中）
1.如果j是k的祖先，那么所求信息就为j和k最后出现的位置之间的信息。
2.如果j不是k的祖先。那么所求信息就为j最先出现的位置以及k最后出现的位置之间的信息，我们发现，j,k的lca不在其中，再把lca加上即可。
那么实现的时候就是用change来表示一个点的出现情况的改变。
然后当做序列上的莫队来做就可以了。
注： 引自DoBelieve的博客
带修改莫队
题目
墨墨购买了一套N支彩色画笔（其中有些颜色可能相同），摆成一排，你需要回答墨墨的提问。墨墨会像你发布如下指令：
1、 Q L R代表询问你从第L支画笔到第R支画笔中共有几种不同颜色的画笔。
2、 R P Col 把第P支画笔替换为颜色Col。
为了满足墨墨的要求，你知道你需要干什么了吗？
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <iostream>
#define N 10005
using namespace std;
int qid=0,tim=0,cx[1000005],res,block[N],ans[N],a[N];
struct ask{int l,r,t,id;}q[N];
struct chan{int x,y;}ch[1005];
int cmp(ask a,ask b){
if (block[a.l]==block[b.l])
{
if (a.r==b.r) return a.t<b.t;
else return a.r<b.r;
}else return a.l<b.l;
}
void change(int now,int i)
{
if (ch[now].x>=q[i].l && ch[now].x<=q[i].r)
{
cx[a[ch[now].x]]--;
if (cx[a[ch[now].x]]==0) res--;
if (cx[ch[now].y]==0) res++;
cx[ch[now].y]++;
}
swap(a[ch[now].x],ch[now].y);
}
int main()
{
int n,m,i;
scanf("%d%d",&n,&m);
int size=sqrt(n);
for (i=1;i<=n;i++) scanf("%d",&a[i]),block[i]=(i-1)/size+1;
for (i=1;i<=m;i++)
{
int l,r;char s[5];
scanf("%s%d%d",s,&l,&r);
if (s[0]=='Q'){
q[++qid].l=l; q[qid].r=r; q[qid].id=qid; q[qid].t=tim;
}
else ch[++tim].x=l,ch[tim].y=r;
}
sort(q+1,q+qid+1,cmp);
int l=0,r=0,now=0;
for (i=1;i<=qid;i++)
{
while (l<q[i].l){cx[a[l]]--;if (cx[a[l]]==0) res--; l++;}
while (l>q[i].l){l--;if (cx[a[l]]==0) res++; cx[a[l]]++;}
while (r<q[i].r){r++;if (cx[a[r]]==0) res++; cx[a[r]]++;}
while (r>q[i].r){cx[a[r]]--;if (cx[a[r]]==0) res--; r--;}
while (now<q[i].t){now++;change(now,i);}
while (now>q[i].t){change(now,i);now--;}
ans[q[i].id]=res;
}
for (i=1;i<=qid;i++) printf("%d\n",ans[i]);
}
我们继续分块。
把二元组L,R变成三元组L,R,x。x是这次询问在修改第几次后。
然后把R所在块看作第二关键字，x看作第三关键字排序即可。
转移时直接恢复（或删除）两次询问之间的修改。如果在区间内还要计算对答案的影响
然而修改的复杂度不同
最优分块方式是每块 N^{2 \over 3}，总共 N^{1\over 3} 块
左指针移动 N*N^{2 \over 3}=N^{5 \over 3} 次
右指针移动 N*N^{2 \over 3}=N^{5 \over 3} 次
修改指针移动(N^{1 \over 3})^2*N=N^{5 \over 3}次
总复杂度 N^{5 \over 3}
在实际操作中，有时取一些什么 \sqrt n*10 之类的奇葩的数可能更快
注： 引自BAJim_H的博客