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

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define ll long long
int n,m;
struct u
{
	int d;
	int z;
	int y;
}c[50000+10];
int a[50000+10];
int fk[50000+10];
int cl[50000+10];
long long fz[50000+10],fm[50000+10],pr;
bool g(const u & aa,const u & bb)
{
	if(fk[aa.z]==fk[bb.z])
	    return aa.y<bb.y;
	return aa.z<bb.z;
}
inline void gx(int ys,int s)
{
	ys=a[ys];
	pr-=(ll)(cl[ys]-1)*cl[ys];
	cl[ys]+=s;
	pr+=(ll)(cl[ys]-1)*cl[ys];
}
ll gcd(ll a,ll b)
{
	while(b!=0)
	{
		int o=b;
		b=a%b;
		a=o;
	}
	return a;
}
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",&a[i]);
	int blocks=550;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d",&c[i].z,&c[i].y);
		fk[i]=(i-1)/blocks+1;
		c[i].d=i;
	}
	sort(c+1,c+1+m,g);
	int z=c[1].z,y=c[1].y;
	for(int i=z;i<=y;i++)
	{
		gx(i,1);
	}
	if(c[1].z==c[1].y)
	{
		fz[c[1].d]=0;
		fm[c[1].d]=1;
	}
	else
	{
		fz[c[1].d]=pr;
		fm[c[1].d]=(ll)(c[1].y-c[1].z)*(c[1].y-c[1].z+1);
	}
	for(int i=2;i<=m;i++)
	{
		if(c[i].z==c[i].y)
		{
			fz[c[i].d]=0;
			fm[c[i].d]=1;
			continue;
		}
		while(z<c[i].z)
		{
			gx(z,-1);
			z++;
		}
		while(z>c[i].z)
		{
			z--;
			gx(z,1);
		}
		while(y>c[i].y)
		{
			gx(y,-1);
			y--;
		}
		while(y<c[i].y)
		{
			y++;
			gx(y,1);
		}
		{
			fz[c[i].d]=(ll)pr;
			fm[c[i].d]=(ll)(c[i].y-c[i].z)*(c[i].y-c[i].z+1);
		}
	}
	for(int i=1;i<=m;i++)
	{
		//printf("%d %d %d\n",i,fz[i],fm[i]);
		if(fz[i]==0)
		    printf("0/1\n");
		else
		{
			ll p=gcd(fm[i],fz[i]);
			fz[i]/=p;
			fm[i]/=p;
			printf("%lld/%lld\n",fz[i],fm[i]);
		}
	}
	/*getchar();
	getchar();*/
}