[ Mo's algorithm ]莫隊算法

對於一些詢問區間答案的資料結構題，我們已經知道了區間[l,r]的答案，且能在極少的時間( $\ord 1$ or $\ord{logN}$ )內得到區間[l+1,r]、[l-1,r]、[l,r+1]、[l,r-1]的答案，題目也准許離線，只要滿足這些性質就可以使用莫隊。

首先我們須將所有詢問記錄下來，將序列分成sqrt(n)塊，找出每筆詢問l所在的塊，每塊內r由小排到大

	#define MAXQ 100000
	struct Q{
	int l,r,i,block;
	inline bool operator<(const Q &b)const{
	return block==b.block?r<b.r:block<b.block;
	}
	}q[MAXQ+5];

view raw struct.cpp hosted with ❤ by GitHub

	lim=1+(int)sqrt(n);
	for(int i=0;i<m;++i){
	scanf("%d%d",&q[i].l,&q[i].r);
	q[i].block=q[i].l/lim;
	q[i].i=i;
	}
	sort(q,q+m);

view raw scanf query.cpp hosted with ❤ by GitHub

這裡n是序列的長度

之後就按造順序一個一個將序列元素在一些維護費用很小的資料結構進行插入刪除，直到等於當前區間為止，此時就可以把這個資料結構的答案存到ans陣列裡，然後結束後一次輸出

	for(int i=0,L=1,R=0;i<m;++i){/*這是閉區間的寫法*/
	while(R<q[i].r)add(s[++R]);
	while(L>q[i].l)add(s[--L]);
	while(R>q[i].r)sub(s[R--]);
	while(L<q[i].l)sub(s[L++]);
	ans[q[i].i]=cur_ans;
	}
	for(int i=0;i<m;++i)printf("%d\n",ans[i]);

view raw find query.cpp hosted with ❤ by GitHub

這裡進行一下簡單的證明:

• 假設序列長度為N，我們將序列每K個分成一塊，在排完序後，左界屬於同一塊的詢問，每次都不會移動操過K次；而左界屬於不同塊的操作，從第i塊移動到第i+1塊最多要移動2*K次，總共分成N/K塊，故移動次數加起來不操過2*K*(N/K)=2*N次，因此左界移動的複雜度為$\ord{Q*K}+\ord N$，Q為詢問次數
• 對於右界，在同一塊內因為是遞增的關係所以移動次數不會操過N次，而最多只有N/K塊，因此複雜度為$\ord{N*N/K}$
• 這個時候我們可以取K=sqrt(N)得到一個複雜度為$\ord{Q*K+N+N*N/K}=\ord{(Q+N)*sqrt(N)}$的方法

這是區間眾數的模板(對於每個詢問l,r輸出區間[l,r]眾數的個數):

	#include<bits/stdc++.h>
	using namespace std;
	#define MAXN 100000
	#define MAXQ 100000
	struct Q{
	int l,r,i,block;
	inline bool operator<(const Q &b)const{
	return block==b.block?r<b.r:block<b.block;
	}
	}q[MAXQ+5];
	int s[MAXN+5],lim;
	int ans[MAXQ+5];
	int u[MAXN+5],cnt[MAXN+5],cur_ans;
	inline void add(int x){
	x=++u[x];
	--cnt[x-1];
	++cnt[x];
	cur_ans=max(cur_ans,x);
	}
	inline void sub(int x){
	x=--u[x];
	--cnt[x+1];
	++cnt[x];
	if(!cnt[cur_ans])--cur_ans;
	}
	int n,m;
	int p[MAXN+5],nn;
	int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
	scanf("%d",&s[i]);
	p[i-1]=s[i];
	}
	sort(p,p+n);
	nn=unique(p,p+n)-p;
	for(int i=1;i<=n;++i)s[i]=lower_bound(p,p+nn,s[i])-p;
	lim=1+(int)sqrt(n);
	for(int i=0;i<m;++i){
	scanf("%d%d",&q[i].l,&q[i].r);
	q[i].block=q[i].l/lim;
	q[i].i=i;
	}
	sort(q,q+m);
	for(int i=0,L=1,R=0;i<m;++i){/*這是閉區間的寫法*/
	while(R<q[i].r)add(s[++R]);
	while(L>q[i].l)add(s[--L]);
	while(R>q[i].r)sub(s[R--]);
	while(L<q[i].l)sub(s[L++]);
	ans[q[i].i]=cur_ans;
	}
	for(int i=0;i<m;++i)printf("%d\n",ans[i]);
	return 0;
	}

view raw range mode.cpp hosted with ❤ by GitHub