记录编号	191890	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	真红之蝶	是否通过	通过
代码语言	C++	运行时间	2.655 s
提交时间	2015-10-09 07:46:44	内存使用	5.25 MiB

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
long long gcd(long long a,long long b)
{
    long long c;
    while(b>0)
    {
        c=b;
        b=a%b;
        a=c;
    }
    return a;
}
struct qes
{
    int l,r,id;
}a[100005];
long long n,m,block[100005],c[100005],tot_block;//s[i]第i种颜色在当前出现了多少次.
long long print_up[100005],print_down[100005],ans,s[100005];
int comp_fk(const qes &a,const qes &b)
{
    return (block[a.l]==block[b.l])?a.r<b.r:a.l<b.l;
}
int comp_id(const qes &a,const qes &b)
{
	return a.id<b.id;
}
long long putup(int pos,int k)
{
    ans-=(long long)s[c[pos]]*(s[c[pos]]-1);//s[i]第i种颜色在当前出现了多少次,去掉上一次的结果
    s[c[pos]]+=k;
    ans+=(long long)s[c[pos]]*(s[c[pos]]-1);
    return ans;
}
int main()
{
	freopen("hose.in","r",stdin);
	freopen("hose.out","w",stdout);
	//freopen("sb","w",stdout);
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;++i)
        scanf("%lld",&c[i]);
    for(int j=1;j<=m;++j)
    {
        scanf("%lld%lld",&a[j].l,&a[j].r);
        a[j].id=j;
    }
    tot_block=(int)sqrt(double(n));
    for(int i=1;i<=n;++i)
        block[i]=(i-1)/tot_block+1;
	sort(a+1,a+m+1,comp_fk);
    for(int i=a[1].l;i<=a[1].r;++i)
        putup(i,1);
    int l=a[1].l,r=a[1].r;
    if(a[1].l==a[1].r)
        print_up[a[1].id]=0,print_down[a[1].id]=1;
    else
        print_up[a[1].id]=ans,print_down[a[1].id]=(long long)(a[1].r-a[1].l+1)*(a[1].r-a[1].l);
    for(int j=2;j<=m;++j)
    {
        while(a[j].r>r)
        {
            r++;
            putup(r,1);
        }
        while(a[j].r<r)
        {
            putup(r,-1);
            r--;
        }
        while(a[j].l>l)
        {
            putup(l,-1);
            l++;
        }
        while(a[j].l<l)
        {
            l--;
            putup(l,1);
        }
        if(a[j].l==a[j].r)
            print_up[a[j].id]=0,print_down[a[j].id]=1;
        else
            print_up[a[j].id]=ans,print_down[a[j].id]=(long long)(a[j].r-a[j].l+1)*(a[j].r-a[j].l);
    }
    sort(a+1,a+m+1,comp_id);
    for(int i=1;i<=m;++i)
    {
		if(print_up[i]==0)
			printf("0/1\n");
		else
		{
			long long u=gcd(print_down[i],print_up[i]);
			print_up[i]/=u;
			print_down[i]/=u;
			printf("%lld/%lld\n",print_up[i],print_down[i]);
		}
    }
    //for(;;);
}/*6 4 1 2 3 3 3 2 2 6 1 3 3 5 1 6*/