莫队算法

参考资料

莫队算法简介 - OI Wiki

例题

小 B 有一个长为 $n$ 的整数序列 $a$ ，值域为 $[1,k]$ 。

他一共有 $m$ 个询问，每个询问给定一个区间 $[l,r]$ ，求：

\sum\limits_{i=1}^k c_i^2

其中 $c_i$ 表示数字 $i$ 在 $[l,r]$ 中的出现次数。

小 B 请你帮助他回答询问。

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;
	}
}q[N];
int a[N];
ll cnt[N],ans[N],sum=0;
void add(int x)
{
	sum+=cnt[x]*2+1;
	cnt[x]++;
}
void del(int x)
{
	sum+=1-cnt[x]*2;
	cnt[x]--;
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n,m,k;
	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>>q[i].l>>q[i].r;
		q[i].id=i;
	}
	sort(q+1,q+m+1);
	int l=1,r=0;
	for(int i=1;i<=m;i++)
	{
		while(l>q[i].l)add(a[--l]);
		while(r<q[i].r)add(a[++r]);
		while(l<q[i].l)del(a[l++]);
		while(r>q[i].r)del(a[r--]);
		ans[q[i].id]=sum;
	}
	for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';
	return 0;
}

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

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

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];
}
pair<ll,ll> ans[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)
		{
			ans[a[i].id]={0,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--]);
		ans[a[i].id]={sum,(r-l+1ll)*(r-l)/2};
	}
	for(int i=1;i<=m;i++)
	{
		auto [p,q]=ans[i];
		if(p==0)
		{
			cout<<0<<'/'<<1<<'\n';
			continue;
		}
		ll g=__gcd(p,q);
		cout<<p/g<<'/'<<q/g<<'\n';
	}
	return 0;
}

参考资料​

例题​

参考资料

例题