记录编号	610502	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	终焉折枝	是否通过	通过
代码语言	C++	运行时间	1.300 s
提交时间	2026-01-03 16:44:26	内存使用	5.04 MiB

#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;

#define int long long
const int MAXN = 50005;
int B = 0;
struct node{
    int l, r, id;
    bool operator < (const node &t) const{
        if(l / B == t.l / B) return r < t.r;
        return l / B < t.l / B;
    }
} q[MAXN];
int cnt[MAXN], col[MAXN];
int n, m, ans1[MAXN], ans2[MAXN], A, BB;

int gcd(int a, int b){
    return (b == 0) ? a : gcd(b, a % b);
}

void add(int x){
    A += cnt[x];
    cnt[x] ++;
}

void del(int x){
    cnt[x] --;
    A -= cnt[x];
}

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;

    B = sqrt(n);

    for(int i = 1;i <= n;i ++){
        cin >> col[i];
    }

    for(int i = 1;i <= m;i ++){
        cin >> q[i].l >> q[i].r;
        q[i].id = i;
    }

    sort(q + 1, q + m + 1);

    for(int l = 1, r = 0, i = 1;i <= m;i ++){
        if(q[i].l == q[i].r){
            ans1[q[i].id] = 0;
            ans2[q[i].id] = 1;
            continue;
        }
        while(l > q[i].l) add(col[-- l]);
        while(l < q[i].l) del(col[l ++]);
        while(r < q[i].r) add(col[++ r]);
        while(r > q[i].r) del(col[r --]);
        BB = (r - l + 1) * (r - l) / 2;
        int g = gcd(A, BB);
        ans1[q[i].id] = A / g;
        ans2[q[i].id] = BB / g;
    }

    for(int i = 1;i <= m;i ++){
        cout << ans1[i] << '/' << ans2[i] << '\n';
    }
    return 0;
}