记录编号	147458	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	天一阁	是否通过	通过
代码语言	C++	运行时间	2.508 s
提交时间	2015-02-01 07:33:25	内存使用	9.47 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define lb(x) (x&(-x))
#define Maxn 200010
#define LL long long
using namespace std;
int n,m,belong[Maxn],blcsiz,a[Maxn];
LL ans1[Maxn],ans2[Maxn];
LL temp=0,tot[Maxn]={0},d;
struct asks{
	int l,r,pos,blc;
}A[Maxn];
bool cmpx(asks a,asks b){
	if(a.blc==b.blc) return a.r<b.r; return a.l<b.l;
}
LL gcd(LL a,LL b){
	return b? gcd(b,a%b):a;
}
void insert(int t,LL v){
	temp-=tot[t]*tot[t];
	tot[t]+=v; temp+=tot[t]*tot[t];
}
int main(){
	freopen("hose.in","r",stdin);
	freopen("hose.out","w",stdout);
	scanf("%d%d",&n,&m); blcsiz=(int)sqrt(n+0.5);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),belong[i]=(i+1)/blcsiz+1;
	for(int i=1;i<=m;i++){
		scanf("%d%d",&A[i].l,&A[i].r);
		A[i].pos=i; A[i].blc=belong[A[i].l];
	}
	sort(A+1,A+m+1,cmpx);
	int l=1,r=0;
	for(int i=1;i<=m;i++){
		while(l>A[i].l) insert(a[--l],1); while(r<A[i].r) insert(a[++r],1);
		while(l<A[i].l) insert(a[l++],-1); while(r>A[i].r) insert(a[r--],-1);
		if(!temp) ans1[A[i].pos]=0,ans2[A[i].pos]=1;
		else{
			LL Pp1=(LL)(r-l+1)*(r-l),Pp0=temp-(r-l+1); d=gcd(Pp0,Pp1);
			ans1[A[i].pos]=Pp0/d; ans2[A[i].pos]=Pp1/d;
		}
	}
	for(int i=1;i<=m;i++) printf("%lld/%lld\n",ans1[i],ans2[i]);
	return 0;
}