一道莫队板子题。
莫队其实就是基于询问的分块算法。
对每一个询问进行排序,整体是左端点排序,块内用上奇偶性排序
如果多了一只袜子$x$的话,那么对答案的贡献从$(v[x]-1)*v[x]/2$到$v[x]*(v[x]+1)/2$,也就是多了一个$v[x]$。
少也是类似的。

return (pos[l]^pos[a.l])?pos[l]<pos[a.l]:((pos[l]&1)?r<a.r:r>a.r);

之后就直接暴力就好了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long 
using namespace std;
const int N=5e4+5;
const int B=225;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)putchar('-'),x=-x;
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll gcd(int a,int b){return b?gcd(b,a%b):a;}
int pos[N],l[N],r[N],a[N],v[N];ll ans[N],bns[N];
struct node{int l,r,id;bool operator <(const node a)const{return (pos[l]^pos[a.l])?pos[l]<pos[a.l]:((pos[l]&1)?r<a.r:r>a.r);}}q[N];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n,m;qr(n),qr(m);
    for(int i=1;i<=n;i++)qr(a[i]);
    for(int i=1;i<=m;i++)qr(q[i].l),qr(q[i].r),q[i].id=i;
    int bl=sqrt(m),sz=bl;
    for(int i=1;i<=sz;i++)
    {
        l[i]=r[i-1]+1;r[i]=i*bl;
        for(int j=l[i];j<=r[i];j++)
            pos[j]=i;
    }
    if(r[sz]<m){l[sz+1]=r[sz]+1,r[++sz]=m;for(int i=l[sz];i<=r[sz];i++)pos[i]=sz;}
    sort(q+1,q+m+1);int L=q[1].l,R=q[1].l-1;ll sum=0;
    for(int i=1;i<=m;i++)
    {
        while(R<q[i].r)sum+=v[a[++R]]++;
        while(L>q[i].l)sum+=v[a[--L]]++;
        while(R>q[i].r)sum-=--v[a[R--]];
        while(L<q[i].l)sum-=--v[a[L++]];
        ans[q[i].id]=sum;
        bns[q[i].id]=1ll*(R-L+1)*(R-L)/2;
    }
    for(int i=1;i<=m;i++)
    {
        ll d=gcd(ans[i],bns[i]);
        qw(ans[i]/d),putchar('/'),qw(bns[i]/d);puts("");
    }
    return 0;
}