#include <bits/stdc++.h>
#define block(i) ((i + b - 1) / b)
#define gcd __gcd
#define N 50034
using namespace std;

typedef long long ll;

struct req{
    int st, en, id, ans;
    req *read(int id0 = 0){scanf("%d%d", &st, &en); id = id0; return this;}
};

int n, q, b;
int i, lp, rp, cur;
ll x, y, d;
int a[N], cnt[N];
char ans[N][20];
req r[N];

bool cmp(const req &x, const req &y){
    int bx = block(x.st), by = block(y.st);
    return bx < by || (bx == by && x.en < y.en);
}

void add(int pos, int val){
    cnt[a[pos]] += val;
    cur = cur + (~val ? cnt[a[pos]] << 1 : -cnt[a[pos]] << 1) - 1;
}

int main(){
    scanf("%d%d", &n, &q);
    b = (int)(sqrt(n) + 1e-6);
    for(i = 1; i <= n; i++)
        scanf("%d", a + i);
    for(i = 0; i < q; i++)
        r[i].read(i);
    sort(r, r + q, cmp);
    lp = 1;
    rp = 0;
    cur = 0;
    memset(cnt, 0, sizeof cnt);
    for(i = 0; i < q; i++){
        while(rp < r[i].en) add(++rp, 1);
        while(rp > r[i].en) add(rp--, -1);
        while(lp < r[i].st) add(lp++, -1);
        while(lp > r[i].st) add(--lp, 1);
        r[i].ans = cur;
    }
    for(i = 0; i < q; i++){
        y = (ll)r[i].en - (ll)r[i].st + 1;
        x = (ll)r[i].ans - y;
        y *= (y - 1);
        d = gcd(x, y);
        sprintf(ans[r[i].id], "%lld/%lld", x /= d, y /= d);
    }
    for(i = 0; i < q; i++)
        puts(ans[i]);
    return 0;
}

C112 莫队算法 P1494 [国家集训队] 小 Z 的袜子

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+10;
int n,m,a[N],B;
LL cnt[N],ans1[N],ans2[N],sum;
struct node{ int l,r,id;}q[N];
bool cmp(const node &n1,const node &n2){return n1.l/B != n2.l/B ? n1.l<n2.l : (n1.l/B & 1 ? n1.r<n2.r : n1.r > n2.r );}
void add(int x)
{
    sum+=cnt[x];
    cnt[x]++;

}
void del(int x)
{
    cnt[x]--;
    sum-=cnt[x];
}
int main()
{
    scanf("%d%d",&n,&m);
    B=sqrt(n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)scanf("%d%d",&q[i].l,&q[i].r),q[i].id=i;
    sort(q+1,q+1+m,cmp);
    sum=0;memset(cnt,0,sizeof(cnt));
    for(int i=1,l=1,r=0;i<=m;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--]);
        ans1[q[i].id]=sum;
        ans2[q[i].id]=1ll*(r-l+1)*(r-l)/2;
    }
    for(int i=1;i<=m;i++)
    {
        if(ans1[i]==0)printf("0/1\n");
        else 
        {
            LL d=__gcd(ans1[i],ans2[i]);
            printf("%lld/%lld\n",ans1[i]/d,ans2[i]/d);
        }
    }
    return 0;
}