记录编号	477355	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	xzz_666	是否通过	通过
代码语言	C++	运行时间	2.441 s
提交时间	2017-12-02 14:56:07	内存使用	2.96 MiB

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cctype>
using namespace std;
#define il inline
#define vd void
#define rg register
#define int long long
il int gi(){
    rg int x=0;rg bool flg=0;rg char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')flg=1;ch=getchar();}
    while(isdigit(ch))x=x*10-'0'+ch,ch=getchar();
    return flg?-x:x;
}
const int maxn=50001,maxm=maxn;
int c[maxn];
struct qq{int l,r,id,ans;}s[maxm];
int n,m,qt,pos[maxn],ans,tot[maxn];
il bool cmp(const qq&a,const qq&b){return (pos[a.l]^pos[b.l])?pos[a.l]<pos[b.l]:a.r<b.r;}
il bool cmp_(const qq&a,const qq&b){return a.id<b.id;}
il int sqr(const int&a){return a*(a-1);}
il int gcd(const int&a,int b){return b?gcd(b,a%b):a;}
main(){
	freopen("hose.in","r",stdin);
	freopen("hose.out","w",stdout);
	n=gi(),m=gi(),qt=sqrt(n);
	for(rg int i=1;i<=n;++i)pos[i]=(i-1)/qt+1;
	for(rg int i=1;i<=n;++i)c[i]=gi();
	for(rg int i=1;i<=m;++i)s[i].l=gi(),s[i].r=gi(),s[i].id=i;
	sort(s+1,s+m+1,cmp);
	s[0].l=s[0].r=1;tot[c[1]]=1;
	for(rg int i=1,j;i<=m;++i){
		for(j=s[i-1].l-1;j>=s[i].l;--j)ans-=sqr(tot[c[j]]),++tot[c[j]],ans+=sqr(tot[c[j]]);
		for(j=s[i-1].r+1;j<=s[i].r;++j)ans-=sqr(tot[c[j]]),++tot[c[j]],ans+=sqr(tot[c[j]]);
		for(j=s[i-1].l;j<s[i].l;++j)ans-=sqr(tot[c[j]]),--tot[c[j]],ans+=sqr(tot[c[j]]);
		for(j=s[i-1].r;j>s[i].r;--j)ans-=sqr(tot[c[j]]),--tot[c[j]],ans+=sqr(tot[c[j]]);
		s[i].ans=ans;
	}
	sort(s+1,s+m+1,cmp_);
	int a,b,_gcd;
	for(rg int i=1;i<=m;++i){
		a=s[i].ans,b=(s[i].r-s[i].l+1)*(s[i].r-s[i].l);
		_gcd=gcd(a,b);
		printf("%lld/%lld\n",a/_gcd,b/_gcd);
	}
	return 0;
}