rt 思路与第一篇题解一样

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e4 + 10;
int n, m, k;
int a[N];
struct stu
{
    int l, r;
    int id;
}ask[N];
int l, r, now;
int cnt[N], ansa[N], ansb[N];

int gcd(int x, int y)
{
    if(y == 0) return x;
    return gcd(y, x % y);
}

bool cmp(stu a1, stu a2)
{
    return a1.l / k ^ a2.l / k ? a1.l < a2. l : a1.r < a2.r;
}

void add(int x)
{
    now -= cnt[a[x]] * cnt[a[x]];
    cnt[a[x]]++;
    now += cnt[a[x]] * cnt[a[x]];
}

void del(int x)
{
    now -= cnt[a[x]] * cnt[a[x]];
    cnt[a[x]]--;
    now += cnt[a[x]] * cnt[a[x]];
}

signed main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    k = sqrt(n);
    for(int i = 1; i <= n; i++) cin >> a[i];
    for(int i = 1; i <= m; i++)
    {
        cin >> ask[i].l >> ask[i].r;
        ask[i].id = i;
    }
    sort(ask + 1, ask + m + 1, cmp);
    for(int i = 1; i <= m; i++)
    {
        while(l > ask[i].l) add(--l);
        while(r < ask[i].r) add(++r);
        while(l < ask[i].l) del(l++);
        while(r > ask[i].r) del(r--);
        if(ask[i].l == ask[i].r)
        {
            ansa[ask[i].id] = 0, ansb[ask[i].id] = 1;
            continue;
        }
        ansa[ask[i].id] = now - (ask[i].r - ask[i].l + 1);
        ansb[ask[i].id] = (ask[i].r - ask[i].l + 1) * (ask[i].r - ask[i].l);
        int x = gcd(ansa[ask[i].id], ansb[ask[i].id]);
        ansa[ask[i].id] /= x, ansb[ask[i].id] /= x;
    }
    for(int i = 1; i <= m; i++) cout << ansa[i] << "/" << ansb[i] << "\n"; 
    return 0;
}