目前的题型概括为三种：普通莫队，树形莫队以及带修莫队。
例题一：小Z的袜子
·述大意：
进行区间询问[l,r]，输出该区间内随机抽两次抽到相同颜色袜子的概率。
·分析：
对于L,R的询问。设其中颜色为x,y,z....的袜子的个数为a,b,c。。。
那么答案即为(a*(a-1)/2+b*(b-1)/2+c*(c-1)/2....)/((R-L+1)*(R-L)/2)
化简得:(a^2+b^2+c^2+...x^2-(a+b+c+d+.....))/((R-L+1)*(R-L))
即：(a^2+b^2+c^2+...x^2-(R-L+1))/((R-L+1)*(R-L))
所以这道题目的关键是求一个区间内每种颜色数目的平方和。
莫队算法是莫涛发明了。莫队算法是离线处理一类区间不修改查询类问题的算法。就是如果你知道了[L,R]的答案。你可以在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案的话。就可以使用莫队算法。
莫队算法只是预先知道了所有的询问。可以合理的组织计算每个询问的顺序以此来降低复杂度。要知道我们算完[L,R]的答案后现在要算[L',R']的答案。由于可以在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案.所以计算[L',R']的答案花的时间为|L-L'|+|R-R'|。如果把询问[L,R]看做平面上的点a(L,R).询问[L',R']看做点b(L',R')的话。那么时间开销就为两点的曼哈顿距离。所以对于每个询问看做一个点。我们要按一定顺序计算每个值。那开销就为曼哈顿距离的和。要计算到每个点。那么路径至少是一棵树。所以问题就变成了求二维平面的最小曼哈顿距离生成树。
但是这种方法编程复杂度稍微高了一点。所以有一个比较优雅的替代品。那就是先对序列分块。然后对于所有询问按照L所在块的大小排序。如果一样再按照R排序。然后按照排序后的顺序计算。为什么这样计算就可以降低复杂度呢。
一、i与i+1在同一块内，r单调递增，所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。
二、i与i+1跨越一块，r最多变化n，由于有n^0.5块，所以这一部分时间复杂度是n^1.5
三、i与i+1在同一块内时变化不超过n^0.5，跨越一块也不会超过2*n^0.5，不妨看作是n^0.5。由于有n个数，所以时间复杂度是n^1.5
于是就变成了O(n^1.5)了。
莫队算法的思路是，离线情况下对所有的询问进行一个美妙的SORT()，然后两个指针l,r（本题是两个，其他的题可能会更多）不断以看似暴力的方式在区间内跳来跳去，最终输出答案。
掌握一个思想基础：两个询问之间的状态跳转。如图，当前完成的询问的区间为[a,b],下一个询问的区间为[p,q],现在保存[a,b]区间内的每个颜色出现次数的sum[]数组已经准备好，[a,b]区间询问的答案Ans1已经准备好，怎样用这些条件求出[p,q]区间询问的Ans2？
考虑指针向左或向右移动一个单位，我们要付出多大的代价才能维护sum[]和Ans(即使得sum[],Ans保存的是当前[l,r]的正确信息)。我们美妙地对图中l,r的向右移动一格进行分析：
如图啦。l指针向右移动一个单位，所造成的后果就是：我们损失了一个绿色方块。那么怎样维护？美妙地，sum[绿色]减去1。那Ans如何维护？先看分母，分母从n2变成(n-1)2，分子中的其他颜色对应的部分是不会变的，绿色却从sum[绿色]2变成(sum[绿色]-1)2 ，为了方便计算我们可以直接向给Ans减去以前该颜色的答案贡献(即sum[绿色]2)再加上现在的答案贡献(即(sum[绿色]-1)2 )。同理，观赏下面的r指针移动，将是差不多的。
·如图r指针的移动带来的后果是，我们多了一个橙色方块。所以操作和上文相似，只不过是sum[橙色]++。
·回归正题地，我们美妙的发现，知道一个区间的信息，要求出旁边区间的信息（旁边区间指的是当前区间的一个指针通过加一减一得到的区间），竟只需要O(1)的时间。
·就算是这样，到这里为止的话莫队算法依旧无法焕发其光彩，原因是：如果我们以读入的顺序来枚举每个询问，每个询问到下一个询问时都用上述方法维护信息，那么在你脑海中会浮现出l,r跳来跳去的疯狂景象，疯狂之处在于最坏情况下时间复杂度为：O(n2)————如果要这样玩，那不如写一个暴力程序。
·“莫队算法巧妙地将询问离线排序，使得其复杂度无比美妙……”在一般做题时我们时常遇到使用排序来优化枚举时间消耗的例子。莫队的优化基于分块思想：对于两个询问，若在其l在同块，那么将其r作为排序关键字，若l不在同块，就将l作为关键字排序（这就是双关键字）。大米饼使用Be[i]数组表示i所属的块是谁。排序如：
·值得强调的是，我们是在对询问进行操作。
·时间复杂度分析（分类讨论思想）：
首先，枚举m个答案，就一个m了。设分块大小为unit。
分类讨论：
①l的移动：若下一个询问与当前询问的l所在的块不同，那么只需要经过最多2*unit步可以使得l成功到达目标.复杂度为：O(m*unit)
②r的移动：r只有在Be[l]相同时才会有序（其余时候还是疯狂地乱跳，你知道，一提到乱跳，那么每一次最坏就要跳n次！），Be[l]什么时候相同？在同一块里面l就Be[]相同。对于每一个块，排序执行了第二关键字：r。所以这里面的r是单调递增的，所以枚举完一个块，r最多移动n次。总共有n/unit个块:复杂度为：O(n*n/unit)
总结：O(n*unit+n*n/unit)（n,m同级，就统一使用n）
根据基本不等式得：当n为sqrt(n)时，得到莫队算法的真正复杂度：
O(n*sqrt(n))
·代码上来了：
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=50003;
int n,m,unit,col[N],Be[N];
ll sum[N],ans;
struct Mo{
int l,r,ID;
ll A,B;
};
Mo q[N];
ll S(ll x)
{
return x*x;
}
ll GCD(ll a,ll b)
{
while(b^=a^=b^=a%=b);
return a;
}
int cmp1(Mo a,Mo b)
{
return Be[a.l]==Be[b.l]?a.r<b.r:a.l<b.l;
}
int CMP(Mo a,Mo b)
{
return a.ID<b.ID;
}
void revise(int x,int add)
{
ans-=S(sum[col[x]]);
sum[col[x]]+=add;
ans+=S(sum[col[x]]);
}
int main()
{
scanf("%d%d",&n,&m);
unit=sqrt(n);
for(int i=1;i<=n;i++){
scanf("%d",&col[i]);
Be[i]=i/unit+1;
}
for(int i=1;i<=m;i++){
scanf("%d%d",&q[i].l,&q[i].r);
q[i].ID=i;
}
sort(q+1,q+m+1,cmp1);
int l=1,r=0;
for(int i=1;i<=m;i++){
while(l<q[i].l){
revise(l,-1);
l++;
}
while(l>q[i].l){
revise(l-1,1);
l--;
}
while(r<q[i].r){
revise(r+1,1);
r++;
}
while(r>q[i].r){
revise(r,-1);
r--;
}
if(q[i].l==q[i].r){
q[i].A=0;
q[i].B=1;
continue;
}
q[i].A=ans-(q[i].r-q[i].l+1);
q[i].B=1LL*(q[i].r-q[i].l+1)*(q[i].r-q[i].l);
ll gcd=GCD(q[i].A,q[i].B);
q[i].A/=gcd;
q[i].B/=gcd;
}
sort(q+1,q+m+1,CMP);
for(int i=1;i<=m;i++){
printf("%lld/%lld\n",q[i].A,q[i].B);
}
return 0;
}