RE 10pts, 自己 OJ 上强数据都能过

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 5e4 + 5;
struct node {
	ll l, r, id;
	ll a, b, k;
} q[maxn];
int n, m, a[maxn], vis[maxn], bl;
bool cmp(node x, node y) { return x.l / bl == y.l / bl ? x.r < y.r : x.l / bl < y.l / bl; }
bool cmp2(node x, node y) { return x.id < y.id; }
ll res;
void add(int pos) {
	vis[a[pos]]++;
	if (vis[a[pos]] > 1) 
		res = res - (vis[a[pos]] - 1) * (vis[a[pos]] - 2) / 2 + (vis[a[pos]]) * (vis[a[pos]] - 1) / 2;
}
void sub(int pos) {
	vis[a[pos]]--;
	if (vis[a[pos]] > 0)
		res = res - (vis[a[pos]] + 1) * vis[a[pos]] / 2 + vis[a[pos]] * (vis[a[pos]] - 1) / 2;
}
int main() {
	scanf("%d %d", &n, &m);
	bl = pow(n, 0.666);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	for (int i = 1; i <= m; i++) {
		scanf("%lld %lld", &q[i].l, &q[i].r);
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp);
	int nowl = 1, nowr = 0;
	for (int i = 1; i <= m; i++) {
		while (nowl > q[i].l) add(nowl - 1), nowl--;
		while (nowr < q[i].r) add(nowr + 1), nowr++;
		while (nowl < q[i].l) sub(nowl), nowl++;
		while (nowr > q[i].r) sub(nowr), nowr--;
		q[i].a = res / __gcd(res, (q[i].r - q[i].l + 1) * (q[i].r - q[i].l) / 2);
		q[i].b = (q[i].r - q[i].l + 1) * (q[i].r - q[i].l) / 2 / __gcd(res, (q[i].r - q[i].l + 1) * (q[i].r - q[i].l) / 2);
	}
	sort(q + 1, q + m + 1, cmp2);
	for (int i = 1; i <= m; i++)
		printf("%lld/%lld\n", q[i].a, q[i].b);
	return 0;
}