Skip to main content

莫队算法

参考资料​

例题​

洛谷 P1494 [国家集训队] 小 Z 的袜子​

洛谷 P1494 [国家集训队] 小 Z 的袜子

有一个长度为 nn 的序列 cic_i。现在给出 mm 个询问，每次给出两个数 l,rl,r，从编号在 ll 到 rr 之间的数中随机选出两个不同的数，求两个数相等的概率。

Code (1)
#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int N=50005;
int len;
struct Node
{
	int l,r,id;
	bool operator<(const Node &rhs) const
	{
		if(l/len!=rhs.l/len)return l<rhs.l;
		return l/len&1?r<rhs.r:r>rhs.r;
	}
}a[N];
ll c[N],cnt[N],sum=0;
void add(int i)
{
	sum+=cnt[i];
	cnt[i]++;
}
void del(int i)
{
	cnt[i]--;
	sum-=cnt[i];
}
ll ans1[N],ans2[N];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m;
	cin>>n>>m;
	len=sqrt(n);
	for(int i=1;i<=n;i++)cin>>c[i];
	for(int i=1;i<=m;i++)
	{
		cin>>a[i].l>>a[i].r;
		a[i].id=i;
	}
	sort(a+1,a+m+1);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		if(a[i].l==a[i].r)
		{
			ans1[a[i].id]=0;
			ans2[a[i].id]=1;
			continue;
		}
		while(l>a[i].l)add(c[--l]);
		while(r<a[i].r)add(c[++r]);
		while(l<a[i].l)del(c[l++]);
		while(r>a[i].r)del(c[r--]);
		ans1[a[i].id]=sum;
		ans2[a[i].id]=(r-l+1ll)*(r-l)/2;
	}
	for(int i=1;i<=m;i++)
	{
		if(ans1[i]==0)
		{
			cout<<0<<'/'<<1<<'\n';
			continue;
		}
		ll g=__gcd(ans1[i],ans2[i]);
		cout<<ans1[i]/g<<'/'<<ans2[i]/g<<'\n';
	}
	return 0;
}