记录编号	586794	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	1.169 s
提交时间	2024-02-27 21:57:35	内存使用	5.35 MiB

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 5e4+10;
int n,m,blo;
int c[N];
struct made{
    int l,r,id;
    bool operator < (const made x)const{
        if(l / blo != x.l / blo)return l < x.l; 
        return (l / blo) & 1 ? r < x.r:r > x.r;
    }
}a[N];
ll sum,s1[N],s2[N],cnt[N];
void add(int x){sum += cnt[x],cnt[x]++;}
void del(int x){cnt[x]--,sum -= cnt[x];}
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
int main(){
    freopen("hose.in","r",stdin);
    freopen("hose.out","w",stdout);
    scanf("%d%d",&n,&m);
    blo = sqrt(n); 
    for(int i = 1;i <= n;i++)scanf("%d",&c[i]);
    for(int i = 1;i <= m;i++)scanf("%d%d",&a[i].l,&a[i].r),a[i].id = i;
    sort(a+1,a+1+m);
    for(int i = 1,l = 1,r = 0;i <= m;i++){
        if(a[i].l == a[i].r){
            s1[a[i].id] = 0,s2[a[i].id] = 1;
            continue;
        }
        while(l > a[i].l)add(c[--l]);
        while(r < a[i].r)add(c[++r]);
        while(l < a[i].l)del(c[l++]);
        while(r > a[i].r)del(c[r--]);
        s1[a[i].id] = sum;
        s2[a[i].id] = 1ll * (r - l + 1) * (r - l) / 2;
    }
    for(int i = 1;i <= m;i++){
        if(s1[i] == 0)s2[i] = 1;
        else{
            ll gc = gcd(s1[i],s2[i]);
            s1[i] /= gc,s2[i] /= gc;
        }
        printf("%lld/%lld\n",s1[i],s2[i]);
    }

	return 0;

}