luogu大佬帮帮本蒟蒻卡进200ms

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=50010;
int n,a[N],k,ret[N],sc[N],L=1,R,ans,cnt[N],lc[N],rc[N],sz;
struct que{
    int l,r,id;
}q[10010];
bool cmp(que x,que y){
    if(sc[x.l]==sc[y.l]) return x.r<y.r;
    return sc[x.l]<sc[y.l];
}
void add(int x){
    cnt[x]++;
    ans+=cnt[x]-1;
}
void del(int x){
    cnt[x]--;
    if(cnt[x]>0) ans-=cnt[x];
}
signed main(){
    scanf("%lld%lld",&n,&k);
    sz=n/sqrt(k*2/3);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sc[i]=(i-1)/sz+1;
    for(int i=1;i<=k;i++) scanf("%lld%lld",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+1+k,cmp);
    for(int i=1;i<=k;i++){
        while(L>q[i].l) add(a[--L]);
        while(R<q[i].r) add(a[++R]);
        while(L<q[i].l) del(a[L++]);
        while(R>q[i].r) del(a[R--]);
        ret[q[i].id]=ans;
        lc[q[i].id]=q[i].l,rc[q[i].id]=q[i].r;
    }
    for(int i=1;i<=k;i++){
        if(lc[i]==rc[i]) printf("0/1\n");
        else if(ret[i]==0) printf("0/1\n");
        else{
            int alen=rc[i]-lc[i]+1;
            int dd=ret[i],ds=(alen*(alen-1))/2;
            int dgcd=__gcd(dd,ds);
            printf("%lld/%lld\n",dd/dgcd,ds/dgcd);
        }
    }
}