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
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N = 5e4 + 10;
int n, q, k;
ll a[N];
ll cnt[N];
struct node{
ll l, r;
ll id, f;
}ask[N];
struct qwq{
ll zi, mu;
}ans[N];
ll gcd(ll a, ll b){
return !b ? a : gcd(b, a%b);
}
bool cmp(node a, node b) {
if(a.l/k == b.l/k) {
return a.r < b.r;
}
return a.l < b.l;
}
ll answer;
void remove(ll pos) {
if(--cnt[a[pos]] > 0) answer += (-2)*(cnt[a[pos]]);
}
void add(ll pos) {
if(++cnt[a[pos]] > 1) answer += 2*(cnt[a[pos]] - 1);
}
void work(ll x, ll y, ll p) {
if(!x) {
ans[p].zi = 0;
ans[p].mu = 1;
} else {
ll k = gcd(x, y);
ans[p].zi = x / k;
ans[p].mu = y / k;
}
}
int main() {
cin >> n >> q;
k = sqrt(n);
for(int i = 1; i <= n; i++) scanf("%lld", &a[i]);
for(ll i = 1; i <= q; i++) {
scanf("%lld%lld", &ask[i].l, &ask[i].r);
ask[i].id = i;
}
sort(ask + 1, ask + q + 1, cmp);
ll curl = 0, curr = 0;
for(int i = 1; i <= q; i++) {
ll L = ask[i].l, R = ask[i].r;
if(L == R) {
ans[ask[i].id].zi = 0;
ans[ask[i].id].mu = 1;
continue;
}
while(curl < L) remove(curl++);
while(curl > L) add(--curl);
while(curr < R) add(++curr);
while(curr > R) remove(curr--);
work(answer, (R-L+1)*(R-L), ask[i].id);
}
for(int i = 1; i <= q; i++) {
printf("%lld/%lld\n", ans[i].zi, ans[i].mu);
}
return 0;
}
|
