莫隊算法簡介

莫隊算法是一種用于高效處理離線區間查詢問題的算法，由莫濤（Mo Tao）在2009年提出。其核心思想是通過對查詢區間進行分塊和排序，利用前一次查詢的結果來減少計算量，從而將時間復雜度優化至接近線性。

莫隊的基本實現步驟：

示范:洛谷P2709 小B的詢問

1.定塊長

將塊長定為 $\sqrt{n}$ 時間復雜度較為平均。
核心代碼：

len=sqrt(n);

2.排序

將詢問輸入并進行排序。
核心代碼：

bool cmp(node x,node y)
{if(x.l/len!=y.l/len)return x.l<y.lelse return x.r<y.r;
}

使用奇偶性優化。
就是如果 $l$ 在的塊是奇數塊，那么 $r$ 按照從小到大排序，否則按照大從小排序。

bool cmp(node x,node y)
{if(x.l/len!=y.l/len)return x.l<y.l;else{if(!((x.l/len)&1))//[0,len]是第一個塊{return x.r<y.r;}else{return x.r>y.r;}}
}

3.移動區間，獲得答案

核心代碼：

for(int i=1,l=1,r=0;i<=m;i++)
{while(b[i].l<l)add(--l);//加上l-1while(b[i].r>r)add(++r);//加上r+1while(b[i].l>l)del(l++);//減去l,將l右移while(b[i].r<r)del(r--);//減去r,將r左移ans[b[i].id]=sum;//注意要用排序前的順序
}

$add$ :

void add(int x)
{if(a[x]<=k)sum-=box[a[x]]*box[a[x]];box[a[x]]++;if(a[x]<=k)sum+=box[a[x]]*box[a[x]];
}

使用平方差公式優化：

void add
{box[a[x]]++;if(a[x]<=k)sum+=2*box[a[x]]-1;
}

$del$ :

void del(int x)
{if(a[x]<=k)sum-=box[a[x]]*box[a[x]];box[a[x]]--;if(a[x]<=k)sum+=box[a[x]]*box[a[x]];
}

使用平方差公式優化：

void del(int x)
{if(a[x]<=k)sum-=2*box[a[x]]-1;box[a[x]]--;
}

4.輸出答案

for(int i=1;i<=m;i++)
{cout<<ans[i]<<'\n';
}

完整代碼

#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 7,M=1e5 + 7;
int n,m,len,num,a[N],sum=0,box[N],k;
int ans[M];
struct node
{int l,r,id;
}b[M];
bool cmp(node x,node y)
{if(x.l/len!=y.l/len)return x.l<y.l;else{if(!((x.l/len)&1)){return x.r<y.r;}else{return x.r>y.r;}}
}
void add(int x)
{box[a[x]]++;if(a[x]<=k)sum+=2*box[a[x]]-1;
}
void del(int x)
{box[a[x]]--;if(a[x]<=k)sum-=2*box[a[x]]+1;
}
int main()
{cin>>n>>m>>k;len=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i];}for(int i=1;i<=m;i++){cin>>b[i].l>>b[i].r;b[i].id=i;}sort(b+1,b+m+1,cmp);for(int i=1,l=1,r=0;i<=m;i++){while(b[i].l<l)add(--l);while(b[i].r>r)add(++r);while(b[i].l>l)del(l++);while(b[i].r<r)del(r--);ans[b[i].id]=sum;}for(int i=1;i<=m;i++){cout<<ans[i]<<'\n';}return 0;
}

核心思想

莫隊算法通過將查詢區間按特定順序排序，利用滑動窗口的思想減少重復計算。通常將序列分成大小為 $\sqrt{n}$ 的塊，并根據塊號和第二關鍵字對查詢進行排序。

適用場景

莫隊算法適用于:查詢離線處理(必須)
可以通過增加或刪除一個元素快速更新區間信息
問題不要求強制在線
基本實現步驟：
將查詢區間按左端點所在塊排序，若在同一塊則按右端點排序。初始化當前區間為[0, -1]，然后依次處理每個查詢，通過移動左右指針來調整區間范圍，同時維護當前區間的統計信息。