思路

维护平方和 $sum$，输出 $\dfrac{sum-(r-l+1)}{(r-l+1)(r-l)}$。

错误类型

RE + WA

代码

#include <cstdio>
#include <cmath>
#include <algorithm> 

using namespace std;
inline int rd(){
	char c;
	bool flag = false;
	while((c = getchar()) < '0' || c > '9')
	    if(c == '-') flag = true;
	int res = c - '0';
	while((c = getchar()) >= '0' && c <= '9')
	    res = (res << 3) + (res << 1) + c - '0';
	return flag ? -res : res;
}
struct Node{
	int l, r, id;
};
struct ans{
    long long a, b;
};
Node q[1000010];
int n, m;
int Do[1000010], a[1000010];
ans Ans[1000010];
int M[1000010];
long long Num = 0;
void Ins(int x){
	M[a[x]]++;
    Num += 2 * M[a[x]] - 1;
}
void Del(int x){
	M[a[x]]--;
	Num -= 2 * M[a[x]] + 1;
}
bool cmp(Node a, Node b){
	return Do[a.l] == Do[b.l] ? a.r < b.r : Do[a.l] < Do[b.l];
}
long long gcd(long long a, long long b){return b ? gcd(b, a % b) : a;}
int main(){
	n = rd();
	m = rd();
	for(int i = 1 ; i <= ceil((double) n / sqrt(n)) ; i++)
		for(int j = (i - 1) * sqrt(n) + 1 ; j <= i * sqrt(n) ; j++)
			Do[j] = i;
	for(int i = 1 ; i <= n ; i++)
		a[i] = rd();
	for(int i = 1 ; i <= m ; i++){
		q[i].l = rd();
		q[i].r = rd();
		q[i].id = i;
	}
	sort(q + 1, q + m + 1, cmp);
	int l = 1, r = 0;
	for(int i = 1 ; i <= m ; i++){
		while(l < q[i].l) Del(l++);
		while(l > q[i].l) Ins(--l);
		while(r < q[i].r) Ins(++r);
		while(r > q[i].r) Del(r--);
		Ans[q[i].id].a = (Num - (r - l + 1));
        Ans[q[i].id].b = (r - l + 1) * (r - l);
        long long GCD = gcd(Ans[q[i].id].a, Ans[q[i].id].b);
        Ans[q[i].id].a /= GCD;
        Ans[q[i].id].b /= GCD;
	}
	for(int i = 1 ; i <= m ; i++){
		printf("%lld/%lld\n", Ans[i].a, Ans[i].b);
	}
	return 0;
}

样例没问题，求调 /kel