记录编号	422368	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	1775.[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	~玖湫~	是否通过	通过
代码语言	C++	运行时间	0.717 s
提交时间	2017-07-09 17:10:44	内存使用	1.55 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define ll long long
const int M=50000+10;
const int qrt=230;
struct DATE{
	int l,r,bh;
}date[M];
int block[M],a[M],cnt[M];
int n,m,l,r;
ll temp,g;
ll ans1[M],ans2[M];
inline int read(){
       int x=0,f=1;char ch=getchar();
       while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
       while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
       return x*f;
}
bool cmp(DATE a,DATE b){
	if(block[a.l]==block[b.l])
		return a.r<b.r;
	return block[a.l]<block[b.l];
}
ll gcd(ll x,ll y){return y==0?x:gcd(y,x%y);}
int DK(){
    freopen("hose.in","r",stdin);
    freopen("hose.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=n;i++){
		a[i]=read();
		block[i]=(i-1)/qrt+1;
	}
	for(int i=1;i<=m;i++){
		date[i].l=read();date[i].r=read();
		date[i].bh=i;
	}
	sort(date+1,date+m+1,cmp);
	l=2;r=1;
	for(int i=1;i<=m;i++){
		if(l>date[i].l){
			while(--l>=date[i].l)
				temp+=cnt[a[l]]++;
			l++;
		}
		if(r<date[i].r){
			while(++r<=date[i].r)
				temp+=cnt[a[r]]++;
			r--;
		}
		if(l<date[i].l)
			while(l<date[i].l){
				temp-=--cnt[a[l]];
				l++;
			}
		if(r>date[i].r)
			while(r>date[i].r){
				temp-=--cnt[a[r]];
				r--;
			}
		ans1[date[i].bh]=temp;
		ans2[date[i].bh]=((ll)(r-l)*(ll)(r-l+1))/2;
		if(!ans2[date[i].bh]){
			ans1[date[i].bh]=0;
			ans2[date[i].bh]=1;
		}
		g=gcd(ans1[date[i].bh],ans2[date[i].bh]);
		ans1[date[i].bh]/=g;
		ans2[date[i].bh]/=g;
	}
	for(int i=1;i<=m;i++)
		printf("%lld/%lld\n",ans1[i],ans2[i]);
	//while(1);
	return 0;
}
int dk=DK();
int main(){
    ;
}