记录编号	574852	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队 2010] 小Z的袜子	最终得分	100
用户昵称	lihaoze	是否通过	通过
代码语言	C++	运行时间	0.663 s
提交时间	2022-08-24 16:04:30	内存使用	5.59 MiB

#include <bits/stdc++.h>

using i64 = long long;

struct Node {
	int l, r, idx;
	i64 p, q;
};

const int N = 50010;
int a[N], b[N], cnt[N];
i64 ans;
Node query[N];

int main() {
	freopen("hose.in", "r", stdin); 
	freopen("hose.out", "w", stdout);
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int n, m, t;
	std::cin >> n >> m;
	t = std::sqrt(n);
	for (int i = 1; i <= n; ++ i)
		std::cin >> a[i];
	for (int i = 1; i <= m; ++ i) {
		auto& [l, r, idx, p, q] = query[i];
		std::cin >> l >> r, idx = i;
		b[i] = (i - 1) / t + 1;
	}
	std::sort(query + 1, query + 1 + m, [](Node x, Node y) {
		return b[x.l] == b[y.l] ? x.r < y.r : x.l < y.l;
	});
	int ll = 1, rr = 0;
	for (int i = 1; i <= m; ++ i) {
		auto& [l, r, idx, p, q] = query[i];
		auto del = [&](int x) { ans += 1 - cnt[x] * 2, -- cnt[x]; };
		auto add = [&](int x) { ans += 1 + cnt[x] * 2, ++ cnt[x]; };
		if (l == r) {
			p = 0, q = 1;
		} else {
			while (ll < l) del(a[ll ++]);
			while (ll > l) add(a[-- ll]);
			while (rr < r) add(a[++ rr]);
			while (rr > r) del(a[rr --]);
			p = ans - (r - l + 1), q = 1LL * (r - l + 1) * (r - l);
			int d = std::__gcd(p, q);
			p /= d, q /= d;
		}
	}
	std::sort(query + 1, query + 1 + m, [](Node a, Node b) {
		return a.idx < b.idx;
	});
	for (int i = 1; i <= m; ++ i)
		std::cout << query[i].p << '/' << query[i].q << '\n';
	return 0;
}