1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44#include <bits/stdc++.h>
using namespace std;

// brute.cpp：每个询问直接统计颜色次数并计算概率，只适合小数据。

const int MAXN = 505;

int n, m;
int color[MAXN];
long long cnt[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> color[i];
    }
    for (int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        for (int c = 0; c <= n; c++) {
            cnt[c] = 0;
        }
        for (int j = l; j <= r; j++) {
            cnt[color[j]]++;
        }
        long long same = 0;
        long long len = r - l + 1;
        for (int c = 1; c <= n; c++) {
            same += cnt[c] * (cnt[c] - 1) / 2;
        }
        if (len == 1) {
            cout << "0/1\n";
        } else {
            long long total = len * (len - 1) / 2;
            long long g = gcd(same, total);
            cout << same / g << '/' << total / g << '\n';
        }
    }

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97#include <bits/stdc++.h>
using namespace std;

const int MAXN = 50005;

struct Query {
    int l, r, id;
};

int n, m;
int block_size;
int color[MAXN];
long long color_count[MAXN]; // 当前区间内每种颜色出现次数。
long long same_pair_count;   // 当前区间内同色无序对数量之和。
long long answer_num[MAXN], answer_den[MAXN];
Query queries[MAXN];

bool cmp_query(const Query &a, const Query &b) {
    int block_a = a.l / block_size;
    int block_b = b.l / block_size;
    if (block_a != block_b) {
        return block_a < block_b;
    }
    if (block_a & 1) {
        return a.r > b.r;
    }
    return a.r < b.r;
}

void add_pos(int pos) {
    int c = color[pos];
    // 新加入一个颜色 c，会和已有 color_count[c] 只同色袜子配成同色对。
    same_pair_count += color_count[c];
    color_count[c]++;
}

void remove_pos(int pos) {
    int c = color[pos];
    color_count[c]--;
    same_pair_count -= color_count[c];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    block_size = max(1, (int)sqrt(n));
    sort(queries + 1, queries + m + 1, cmp_query);

    int cur_l = 1, cur_r = 0;
    for (int i = 1; i <= m; i++) {
        int l = queries[i].l;
        int r = queries[i].r;
        while (cur_l > l) {
            cur_l--;
            add_pos(cur_l);
        }
        while (cur_r < r) {
            cur_r++;
            add_pos(cur_r);
        }
        while (cur_l < l) {
            remove_pos(cur_l);
            cur_l++;
        }
        while (cur_r > r) {
            remove_pos(cur_r);
            cur_r--;
        }

        long long len = r - l + 1;
        if (len == 1) {
            answer_num[queries[i].id] = 0;
            answer_den[queries[i].id] = 1;
        } else {
            long long total_pair = len * (len - 1) / 2;
            long long g = gcd(same_pair_count, total_pair);
            answer_num[queries[i].id] = same_pair_count / g;
            answer_den[queries[i].id] = total_pair / g;
        }
    }

    for (int i = 1; i <= m; i++) {
        cout << answer_num[i] << '/' << answer_den[i] << '\n';
    }

    return 0;
}