记录编号	192041	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	落尘	是否通过	通过
代码语言	C++	运行时间	2.712 s
提交时间	2015-10-09 17:49:44	内存使用	2.23 MiB

#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <fstream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
#include <ctime>
#include <map>
#define LL long long int
using namespace std;
ifstream fin("hose.in");
ofstream fout("hose.out");
static const int MAXN=50001;
int N,M,Base;
struct Quary{
	int L,R,pos;
	LL ANSS,ANSM;
}Q[MAXN];
int color[MAXN],p[MAXN],num[MAXN];
LL Pr;
bool COMP1(Quary A,Quary B){
	if(p[A.L]==p[B.L]) return A.R<B.R;
	return A.L<B.L;
}
bool COMP2(Quary A,Quary B){return A.pos<B.pos;}
LL GCD(LL A,LL B){return B==0?A:GCD(B,A-A/B*B);}
void add(int pos,int d){
	Pr-=(LL)num[color[pos]]*(num[color[pos]]-1);
	num[color[pos]]+=d;
	Pr+=(LL)num[color[pos]]*(num[color[pos]]-1);
}
void ASK(Quary& A){
	A.ANSS=Pr;
	A.ANSM=(LL)(A.R-A.L)*(A.R-A.L+1);
	LL gcd(GCD(A.ANSS,A.ANSM));
	A.ANSS/=gcd; A.ANSM/=gcd;
}
void INIT(){
	fin>>N>>M;
	Base=sqrt(N);
	for(int i(1);i<=N;++i){
		fin>>color[i];
		p[i]=(i-1)/Base+1;
	}
	for(int i(1);i<=M;++i){
		fin>>Q[i].L>>Q[i].R;
		Q[i].pos=i;
		Q[i].ANSS=Q[i].ANSM=0;
	}
	sort(Q+1,Q+M+1,COMP1);
	int l=1,r=0;
	for(int i(1);i<=M;++i){
		if(Q[i].L==Q[i].R){
			Q[i].ANSS=0; Q[i].ANSM=1;
			continue;
		}
		for(;l>Q[i].L;--l) add(l-1,1);
		for(;l<Q[i].L;++l) add(l,-1);
		for(;r<Q[i].R;++r) add(r+1,1);
		for(;r>Q[i].R;--r) add(r,-1);
		ASK(Q[i]);
//fout<<(double)clock()<<endl;
	}
	sort(Q+1,Q+M+1,COMP2);
	for(int i(1);i<=M;++i)
		fout<<Q[i].ANSS<<"/"<<Q[i].ANSM<<endl;
}
int main(){
	INIT();
	fin.close();
	fout.close();
    return 0;
}