lp1494 国家集训队 小Z的袜子

令颜色为\(c_i\)为第\(i\)种颜色在给定区间内出现的次数。
则，题目所求为：
$$\frac{\sum_{i=1}^{n}c_{i}(c_{i}-1)}{(r-l)(r-l+1)}$$
展开可以得到：
$$\frac{\sum_{i=1}^{n}c_{i}^2-\sum_{i=1}^{n}c_{i}}{(r-l)(r-l+1)}$$
由性质可得：
$$\sum_{i=1}^{n}c_{i}=r-l+1$$
故而，我们需要求的仅有：
$$\sum_{i=1}^{n}c_{i}^2$$
对于这个式子的求法，我们很容易可以想到莫队。
我们考虑一个区间添加上一个数与删除一个数造成的影响。
令修改的颜色为\(x\)，则：
$$\Delta v=\sum_{i=1}^{n}c_{i}^2-c_{x}^{2}+(c_{x}±1)^2-\sum_{i=1}^{n}c_{i}^2$$
展开可得：
$$\Delta v=1±2c_{x}$$

下面考虑莫队。
莫队的原理大致是，将原数列分块，然后将询问以左端点在原数列中的块为第一关键字，右端点为第二关键词来排序。
虽然说它是一种优化后的暴力，但是，若令一次修改的复杂度是\(f_{n}\)，根据最小直线斯坦纳树的性质，可以证明这么做的复杂度是 \(O(f_{n} n \sqrt{m})\)，可以通过此题。
依据毒瘤lxl的说法，莫队最快的分块大小是\(n/\sqrt{m*2/3}\)
故而我们对原数列分块完以后，将询问排序。然后开始移动区间。
扫一遍即可。
另外就是一个小优化，排序的时候分奇偶排序，也就是说，奇数块右端点递增，偶数块右端点递减。
原理很简单，就是移过去再移回来，路上的点都扫了一遍。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
int BLOCK;
int belong[50005];
struct Query{
	int l;
	int r;
	int id;
	int len;
	inline bool operator <(const Query &B)const{
		return (belong[l]^belong[B.l])?(belong[l]<belong[B.l]):((belong[l]&1)?r<B.r:r>B.r);
	}
}q[50005];
long long tot=0;
int cnt[50005];
inline void add(int X){
	tot+=(cnt[X]<<1|1);
	++cnt[X];
}
inline void del(int X){
	tot+=(1-(cnt[X]<<1));
	--cnt[X];
}
inline long long Gcd(long long A,long long B){
	return B?Gcd(B,A%B):A;
}
long long ans1[50005],ans2[50005];
int n,m,a[50005];
void init(){
	scanf("%d%d",&n,&m);
	BLOCK=n/std::sqrt(m*2.0/3.0); 
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
	}
	for(int i=1;i<=m;++i){
		scanf("%d%d",&q[i].l,&q[i].r);
		q[i].id=i;
		q[i].len=q[i].r-q[i].l+1;
		ans2[i]=1;
	}
	for(int i=1;i<=n;++i){
		belong[i]=(i-1)/BLOCK+1;
	}
	std::stable_sort(q+1,q+1+m);
	int l=q[1].l,r=q[1].l-1;
	long long nwgcd;
	for(int i=1;i<=m;++i){
		while(l<q[i].l){
			del(a[l]);
			++l;
		}
		while(l>q[i].l){
			--l;
			add(a[l]);
		}
		while(r>q[i].r){
			del(a[r]);
			--r;
		}
		while(r<q[i].r){
			++r;
			add(a[r]);
		}
		if(tot!=q[i].len){
			ans1[q[i].id]=tot-q[i].len,ans2[q[i].id]=1LL*(q[i].r-q[i].l)*q[i].len;
			nwgcd=Gcd(ans1[q[i].id],ans2[q[i].id]);
			ans1[q[i].id]/=nwgcd,ans2[q[i].id]/=nwgcd;
		}
	}
	for(int i=1;i<=m;++i){
		printf("%lld/%lld\n",ans1[i],ans2[i]);
	}
}

int main(){
	init();
	return 0;
}