记录编号	191818	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	2.515 s
提交时间	2015-10-08 21:22:54	内存使用	2.60 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
#define LL long long
struct dd{
	int left,right,id;
}jie[50006];
LL as[50006],bs[50006],ans,kuai[50006],num[50006];
int n,m,color[50006];
bool comp(const dd & a,const dd & b){
	if(kuai[a.left]==kuai[b.left]) return a.right<b.right;
	return a.left<b.left;
}
void update(int rt,int po){
	ans-=num[color[rt]]*(num[color[rt]]-1);
	num[color[rt]]+=po;
	ans+=num[color[rt]]*(num[color[rt]]-1);
	return;
}
LL gcd(LL x,LL y){
	return(y==0)?(x):(gcd(y,x%y));
}
int main(){
    freopen("hose.in" ,"r",stdin ) ;
	freopen("hose.out","w",stdout) ;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) scanf("%d",&color[i]);
	for(int i=1;i<=m;++i){
	  scanf("%d%d",&jie[i].left,&jie[i].right); jie[i].id=i;
	}
	int bol=550;
	for(int i=1;i<=n;++i){
		kuai[i]=((i-1)/bol)+1;
	}
	sort(jie+1,jie+m+1,comp);
	int l=jie[1].left,r=jie[1].right;
	for(int i=l;i<=r;++i) update(i,1);
	if(l==r) { as[jie[1].id]=0;  bs[jie[1].id]=1;}
	else { as[jie[1].id]=ans;  bs[jie[1].id]=(LL)(r-l)*(r-l+1); }
	for(int i=2;i<=m;++i){
		while(l<jie[i].left) update(l++,-1);
		while(l>jie[i].left) update(--l,1);
		while(r>jie[i].right) update(r--,-1);
		while(r<jie[i].right) update(++r,1);
		if(jie[i].right==jie[i].left) { as[jie[i].id]=0; bs[jie[i].id]=1;}
		else{ as[jie[i].id]=ans;  bs[jie[i].id]=(LL)(jie[i].right-jie[i].left)*(jie[i].right-jie[i].left+1);}
	}
	for(int i=1;i<=m;++i){
	  if(as[i]==0) puts("0/1");
	  else{
		 LL k=gcd(as[i],bs[i]);
		 as[i]/=k; bs[i]/=k;
		 printf("%lld/%lld\n",as[i],bs[i]);
	  }
	}
	getchar();getchar();
}