【BZOJ2038】【2009国家集训队】小Z的袜子(hose)

  对于一个询问区间\([L,R]\)，设\(cnt[i]\)该区间内表示颜色为i的袜子数，\(len=R-L+1\)表示区间长度，答案为\[\frac{{\sum\limits_{i = 1}^{\max \{ c\} } {(\frac{{cnt[i]*(cnt[i] - 1)}}{2})} }}{{\frac{{len*(len - 1)}}{2}}}\]

  稍微化简一下就是\[\frac{{\sum\limits_{i = 1}^{\max \{ c\} } {(cnt{{[i]}^2} - cnt[i])} }}{{le{n^2} - len}}\]

  这个化简也没有什么卵用，反正就是莫队做一遍就好了。

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=50010;

int GCD(int x,int y)
{
	int md;
	while (y) md=x%y,x=y,y=md;
	return x;
}

struct Query
{
	int l,r,block,id;
	bool operator< (const Query &b) const {return block<b.block || block==b.block && r<b.r;}
}Q[maxn];

int c[maxn];
int cnt[maxn];
int ansa[maxn],ansb[maxn];
int n,m,V;

int main()
{
	scanf("%d%d",&n,&m);
	V=sqrt(n)+1;
	for (int i=1;i<=n;i++) scanf("%d",&c[i]);
	for (int i=1;i<=m;i++) scanf("%d%d",&Q[i].l,&Q[i].r),Q[i].block=Q[i].l/V,Q[i].id=i;
	sort(Q+1,Q+1+m);
	int res=0;
	for (int i=1,l=1,r=0;i<=m;i++)
	{
		while (l<Q[i].l) cnt[c[l]]--,res-=cnt[c[l]],l++;
		while (l>Q[i].l) l--,res+=cnt[c[l]],cnt[c[l]]++;
		while (r<Q[i].r) r++,res+=cnt[c[r]],cnt[c[r]]++;
		while (r>Q[i].r) cnt[c[r]]--,res-=cnt[c[r]],r--;
		if (res==0) {ansa[Q[i].id]=0,ansb[Q[i].id]=1;continue;}
		int M=(LL)(Q[i].r-Q[i].l+1)*(Q[i].r-Q[i].l)/2;
		int g=GCD(M,res);
		ansa[Q[i].id]=res/g,ansb[Q[i].id]=M/g;
	}
	for (int i=1;i<=m;i++) printf("%d/%d\n",ansa[i],ansb[i]);
	return 0;
}