莫隊算法可用於解決一類可離線且在得到區間[l,r][l,r]的答案後，能在O(1)O(1)或O(log2n)O(log2n)得到區間[l,r+1][l,r+1]或[l−1,r][l−1,r]的答案的問題
先看這樣一個問題：
給出n個數字，m次詢問，每次詢問在區間[li,ri][li,ri]之間任選兩個數字相等的概率是多少。（n,q<=50000）（小z的襪子）
在區間[l,r][l,r]中，這個概率是：
由於沒有加和性質，傳統的線段樹什麼的完全派不上用場了呢！
考慮分子，因為C(2,x)=x2−x2C(2,x)=x2−x2，所以分子=∑vi=1f(i)2−∑vi=1f(i)2∑i=1vf(i)2−∑i=1vf(i)2
顯然 ∑vi=1f(i)=r−l+1∑i=1vf(i)=r−l+1
若得知區間[l,r][l,r]的答案怎麼求區間[l,r+1][l,r+1]的答案呢？仔細想想。恩，有了。區間[l,r+1][l,r+1]與區間[l,r][l,r]相比只多了一個元素Z，這種改動是很小的，那麼前式中分子的值S=S0−f(Z)2+(f(Z)+1)2−1=S0+2∗f(Z)S=S0−f(Z)2+(f(Z)+1)2−1=S0+2∗f(Z)，同時++f(z)，恩，O(1)O(1)的。這樣的話，在處理下一個詢問[li,ri][li,ri]時，復雜度就是O(|r−ri|+|l−li|)O(|r−ri|+|l−li|)的。同樣的方法，也可以在O(1)O(1)內求出[l−1,r][l−1,r]，[l+1,r][l+1,r],[l,r−1][l,r−1]。這樣的方法對於隨機數據表現是很好的，但也不難給出故意卡你的數據。
這時，就需要莫隊算法來撐腰了，這也是莫隊算法優化的精髓。
注意到，每個區間可以抽象成平面中的點，每次轉移的花費都相當與從某點到另一點的曼哈頓距離的長度。恩，所以呢？
所以我們花費的便是這些平面中的點聯通的曼哈頓距離。平面點的曼哈頓最小生成樹！
對！但平面點的曼哈頓最小生成樹怎麼求呢？枚舉兩兩點連接O(n2)O(n2)，毫無意義。其實平面點的曼哈頓最小生成樹有基於平面區域劃分的O(nlog2n)O(nlog2n)的求法，但我們有更簡潔的方法。對，分塊！
確實，利用分塊，我們可以實現O(nn√)O(nn)的時間復雜度。雖然求解平面點的曼哈頓最小生成樹是O(nlog2n)O(nlog2n)的，但根據莫隊論文中的證明，用到這裡時，仍然是O(nn√)O(nn)，只不過常數小一些罷了。
分塊的做法：
取x=(√n)x=(n)，以[1,x],[x+1,2x],[2x+1,3x]...[1,x],[x+1,2x],[2x+1,3x]...分塊
用pos數組維護端點i在第pos[i]塊中，然後就搞呗。
這樣搞：
1)：排序，以左段點所在的塊為第一關鍵字，以右端點為第二關鍵字
2)：從左往右處理詢問（離線）
3)：不斷調整l,r的位置並同時修改
時間復雜度證明：
右端點移動：
首先我們考慮一個塊裡面的轉移情況
由於一個塊裡面的詢問都按右端點排序
所以我們右端點在一個塊裡面最多移動n次
有 O(n√)O(n)個塊，那麼同一個塊內的右端點移動最多就是O(nn√)O(nn)
然後考慮從一個塊到另一個塊導致的右端點變化
最壞情況，右端點由n到1，那麼移動n次
有 O(n√)O(n)個塊
那麼從一個塊到另一個塊的事件只會發生O(n√)O(n)次……
所以這種右端點移動的次數也是O(nn√)O(nn)次
沒有別的事件導致右端點移動了
左端點移動：
同一個塊裡面，由於左端點都在一個長度為O(n√)O(n)的區間裡面
所以在同一塊裡面移動一次，左端點最多變化O(n√)O(n)
總共有n個詢問……
所以同一塊裡面的移動最多n次
那麼同一個塊裡面的左端點變化最多是O(nn√)O(nn)的
考慮跨越塊
每由第i個塊到第i+1個塊，左端點最壞加上O(n√)O(n)
總共能加上O(n√)O(n)次
所以跨越塊導致的左端點移動是O(n)O(n)的
綜上，分塊做法是O(n∗n√)O(n∗n)。
莫隊算法在解決離線區間詢問幾乎是無敵的。
恩，幾乎只要能離線，用分塊的莫隊算法都能取得一個令人滿意的的解法。
所以就有很多擴展（解決線段樹等數據結構由於需要區間加和性而不能解決的問題），如區間眾數，平均數什麼的。
恩。棒！
附:
[BZOJ]2038 小Z的襪子 分塊 莫隊算法
#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
const int maxn = 50000 + 500;
typedef long long LL;
LL gcd(LL a,LL b)
{
return (b==0)?a:gcd(b,a%b);
}
int pos[maxn];
int col[maxn];
int f[maxn];
int n,m;
struct Query
{
int l,r,id;
LL a,b;
friend bool operator < (const Query &R,const Query &T)
{
return pos[R.l]<pos[T.l] || (pos[R.l]==pos[T.l] && R.r<T.r);
}
void modify()
{
LL k=gcd(a,b);
a/=k,b/=k;
}
}Q[maxn];
bool cmp_id(const Query &a,const Query &b)
{
return a.id<b.id;
}
void init()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
scanf("%d",&col[i]);
int limit=(int)sqrt((double)n+0.5);
for(int i=1;i<=n;++i)
pos[i]=(i-1)/limit+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);
}
void modify(int p,LL &ans,int add)
{
ans=ans+2*add*f[col[p]]+1;
f[col[p]]+=add;
}
void solve()
{
LL ans=0;
int l=1,r=0;
for(int i=1;i<=m;++i)
{
if(r<Q[i].r)
{
for(r=r+1;r<Q[i].r;++r)
modify(r,ans,1);
modify(r,ans,1);
}
if(Q[i].l<l)
{
for(l=l-1;Q[i].l<l;--l)
modify(l,ans,1);
modify(l,ans,1);
}
if(Q[i].r<r)
for(;Q[i].r<r;--r)
modify(r,ans,-1);
if(l<Q[i].l)
for(;l<Q[i].l;++l)
modify(l,ans,-1);
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=(LL)(Q[i].r-Q[i].l+1)*(Q[i].r-Q[i].l);
Q[i].modify();
}
sort(Q+1,Q+m+1,cmp_id);
for(int i=1;i<=m;++i)
printf("%lld/%lld\n",Q[i].a,Q[i].b);
}
int main()
{
init();
solve();
return 0;
}
Refrence:
http://foreseeable97.logdown.com/posts/158522-233333
http://ydcydcy1.blog.163.com/blog/static/21608904020134411543898/
http://vawait.com/manhattanmst/
http://blog.csdn.net/huzecong/article/details/8576908
