题目链接：https://www.luogu.org/problemnew/show/P1494
题目大意：

思路：

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
//由块号寻找第一个块元素的下标

const int maxn=50050;

struct node
{
    LL L, R, k;
}q[maxn];

struct d
{
    LL fz;
    LL fm;
}ans[maxn];

int pos[maxn];
LL sum[maxn];
int a[maxn];

bool cmp(node a, node b){

    return pos[a.L]==pos[b.L]?(pos[a.L]&1)?a.R<b.R:a.R>b.R:pos[a.L]<pos[b.L];
}

int n, m, k, Len;
int L=1, R=0;
LL ANS=0;

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

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

int main()
{
    scanf("%d",&n);
    scanf("%d",&m);
    Len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        pos[i]=i/Len;
    }
    for(int i=1;i<=m;i++)
    {
        scanf("%lld%lld",&q[i].L,&q[i].R);
        q[i].k=i;
    }

    sort(q+1, q+1+m, cmp);
    for(int i=1;i<=m;i++)
    {
        while(L<q[i].L)
        {
            del(L);
            L++;
        }
        while(L>q[i].L)
        {
            L--;
            add(L);
        }
        while(R<q[i].R)
        {
            R++;
            add(R);
        }
        while(R>q[i].R)
        {
            del(R);
            R--;
        }

        LL fz=ANS-(q[i].R-q[i].L+1), fm=(q[i].R-q[i].L+1)*(q[i].R-q[i].L);

        if(fz==0)
        {
            ans[q[i].k].fz=0;
            ans[q[i].k].fm=1;
        }
        else
        {
            ans[q[i].k].fz=fz/__gcd(fz, fm);
            ans[q[i].k].fm=fm/__gcd(fz, fm);
        }
    }
    for(int i=1;i<=m;i++)
    {
        printf("%lld/%lld\n",ans[i].fz, ans[i].fm);
    }

    return 0;
}