维护平方和 sum,输出 (r−l+1)(r−l)sum−(r−l+1)。
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