莫队算法学习笔记+例题

莫队算法是用来解决离线区间问题的暴力解法，但是这种暴力解法是经过分块优化的，朴素暴力解法的时间复杂度是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;
}