莫隊算法學習筆記+例題

莫隊算法是用來解決離線區間問題的暴力解法，但是這種暴力解法是經過分塊優化的，樸素暴力解法的時間複雜度是O(n*m)，而莫隊算法的複雜度一般來說就是O(n*sqrt(m))。莫隊算法的核心，我的了解就是相鄰區間狀态的轉移，前提是狀态的轉移計算時間必須要是O(1)，否則的話就會出現複雜度爆炸。比如現在知道了區間[L, R]的解，那麼如果要使用莫隊算法，必須要在O(1)的時間複雜度下分别計算出區間[L-1,R]、[L+1,R]、[L,R-1]、[L,R+1]的解。

例題

洛谷P1494 [國家集訓隊]小Z的襪子 【莫隊+組合數】

【https://www.luogu.org/problemnew/show/P1494 】

題意：小Z有n隻很多種顔色的襪子，分别按順序編号，有m次詢問，每次詢問在襪子序号為[L,R]之間随機選兩隻襪子有多少機率可以拿到顔色相同的。

每個區間内拿到相同襪子的機率：

C c n t [ 1 ] 2 + C c n t [ 2 ] 2 + … … + C c n t [ n ] 2 C R − L + 1 2 \frac{C^{2}_{cnt[1]}+C^{2}_{cnt[2]}+……+C^{2}_{cnt[n]}}{C^{2}_{R-L+1}} CR−L+12​Ccnt[1]2​+Ccnt[2]2​+……+Ccnt[n]2​​

cnt[i]表示區間内第i中顔色的襪子有多少種

每次在進行區間狀态的轉移的時候計算一下組合數然後簡單處理一下就好了

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn = 5e4+7;
struct QUERY{
	int lt,rt,id;
}query[maxn];
int n,m,block,seq[maxn],cnt[maxn];
LL res[maxn][2],ans;

bool cmp(QUERY a,QUERY b){
	if(a.lt/block==b.lt/block) return a.rt<b.rt;
	else return a.lt<b.lt;
}
LL Comb(int x){
	return (LL)x*(x-1)/2;
}
inline LL gcd(LL a,LL b){
	return b?gcd(b,a%b):a;
}
inline void add(int x){
	ans+=Comb(cnt[x]+1)-Comb(cnt[x]);
	cnt[x]++;
}
inline void sub(int x){
	ans+=Comb(cnt[x]-1)-Comb(cnt[x]);
	cnt[x]--;
}
void solve(){
	int l=1,r=1;
	cnt[seq[1]]++;
	for(int i=1;i<=m;i++){
		while(l<query[i].lt) sub(seq[l++]);
		while(l>query[i].lt) add(seq[--l]);
		while(r<query[i].rt) add(seq[++r]);
		while(r>query[i].rt) sub(seq[r--]);
		res[query[i].id][0] = ans;
		res[query[i].id][1] = Comb(r-l+1);
	}
}
int main(){
	scanf("%d %d",&n,&m);
	block = sqrt(n);
	for(int i=1;i<=n;i++) scanf("%d",&seq[i]);
	for(int i=1;i<=m;i++){
		scanf("%d %d",&query[i].lt,&query[i].rt);
		query[i].id = i;
	}
	sort(query+1,query+1+m,cmp);
	solve();
	for(int i=1;i<=m;i++){
		if(res[i][0]==0) printf("0/1\n");
		else{
			LL del = gcd(res[i][0],res[i][1]);
			printf("%lld/%lld\n",res[i][0]/del,res[i][1]/del);
		}
	}
	return 0;
}
           

HDU5145 NPY and girls 【莫隊+除法取模逆元】

【http://acm.hdu.edu.cn/showproblem.php?pid=5145 】

題意：NPY有n個女朋友，編号從1到n，分布在各個班級中，給出m個區間[Li,Ri]，每次NPY都想找區間[Li,Ri]中的女朋友約會，要求求出班級排列不同的約會的方案有幾種（如果兩個女朋友在同一個班，那麼交換約會順序的話還是算一種方案）

先考慮暴力求解的狀況：

假設在區間[L,R]之間，cnt[1],cnt[2],cnt[3]…cnt[i]…cnt[maxn]分别表示區間[L,R]之間在班級 i 中的女朋友的數量，那麼此時方案數量是：

A N S = C R − L + 1 c n t [ 1 ] ⋅ C R − L + 1 − c n t [ 1 ] c n t [ 2 ] ⋅ … … ⋅ C R − L + 1 − ∑ k = 1 i − 1 c n t [ i ] ANS = C_{R-L+1}^{cnt[1]}·C_{R-L+1-cnt[1]}^{cnt[2]}·……·C_{R-L+1-\sum_{k=1}^{i-1}}^{cnt[i]} ANS=CR−L+1cnt[1]​⋅CR−L+1−cnt[1]cnt[2]​⋅……⋅CR−L+1−∑k=1i−1​cnt[i]​

現在簡單推導一下區間改變了之後對方案數的影響：

如果區間改變後一個值的出現次數增加了一次：

最終方案數會改變成ANS*(R-L+1+1)/(cnt[i]+1)

而如果其中一個值出現次數減少了一次

方案數變成ANS*cnt[i]/(R-L+1)

（ANS為已知區間的方案數）

由于1000000007是個大質數，是以對于除法的取模采取乘逆元的辦法

先根據費馬小定理預處理出1~30000之間所有數對1000000007的逆元，然後莫隊分塊計算就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
const LL mod = 1e9+7;
const int maxn = 3e4+7;
int block;
struct QUERY{
	int lt,rt,id;
	bool operator < (const QUERY &x){
		if(lt/block==x.lt/block) return rt<x.rt;
		else return lt<x.lt;
	}
}query[maxn];
int T,n,m,seq[maxn];
LL inv[maxn],res[maxn],ans,cnt[maxn];
LL qpow_mod(LL a,LL b){
	LL tmp = 1;
	while(b){
		if(b&1) tmp = tmp*a%mod;
		b>>=1;
		a = a*a%mod;
	}
	return tmp;
}
void inv_table(){
	for(int i=1;i<maxn;i++) inv[i] = qpow_mod(i,mod-2);
}
inline void add(LL d,LL x){
	ans = ans*(d+1)%mod*inv[++cnt[x]]%mod;
}
inline void sub(LL d,LL x){
	ans = ans*(cnt[x]--)%mod*inv[d]%mod;
}
void solve(){
	int l=1,r=0;
	ans = 1;
	for(int i=1;i<=m;i++){
		while(query[i].lt<l){
			LL d = r-l+1;
			add(d,seq[--l]);
		}
		while(query[i].rt>r){
			LL d = r-l+1;
			add(d,seq[++r]);
		}
		while(query[i].lt>l){
			LL d = r-l+1;
			sub(d,seq[l++]);
		} 
		while(query[i].rt<r){
			LL d = r-l+1;
			sub(d,seq[r--]);
		} 
		
		res[query[i].id] = ans;
	}
}
int main(){
	inv_table();
	scanf("%d",&T);
	while(T--){
		memset(cnt,0,sizeof(cnt));
		scanf("%d %d",&n,&m);
		block = sqrt(n);
		for(int i=1;i<=n;i++) scanf("%d",&seq[i]);
		for(int i=1;i<=m;i++){
			scanf("%d %d",&query[i].lt,&query[i].rt);
			query[i].id = i;
		}
		sort(query+1,query+1+m);
		solve();
		for(int i=1;i<=m;i++) printf("%I64d\n",res[i]);
	}
	return 0;
}