题目链接：

题意：给出n个袜子。m个询问，每个询问一个区间[L,R]，询问这个区间中任意拿出两个袜子相同的概率。

思路：令x=sqrt(n)，每x个分成一组。将询问按照L放到相应的组中。同一组内按照R升序。这样一组内最多向右移动n的长度，向左移动都在本组内，最大x。总复杂度n*sqrt(n)。

struct node

{

    int L,R,id;

    node(){}

    node(int _L,int _R,int _id)

    {

        L=_L;

        R=_R;

        id=_id;

    }

};

int a[N],n,m;

vector<node> V[N];

int cmp(node a,node b)

{

    return a.R<b.R;

}

u64 ans[N];

int b[N],L[N],R[N];

u64 C(int x)

{

    return (u64)x*(x-1)/2;

}

u64 Gcd(u64 x,u64 y)

{

    if(!y) return x;

    return Gcd(y,x%y);

}

int main()

{

    RD(n,m);

    int i;

    FOR0(i,n) RD(a[i]);

    int len=sqrt(1.0*n+0.5);

    int s=n/len+(n%len!=0);

    int x,y;

    FOR1(i,m)

    {

        RD(x,y); x--,y--; L[i]=x; R[i]=y;

        V[x/len].pb(node(x,y,i));

    }

    int j,k,curL,curR;

    u64 pre;

    FOR0(i,s)

    {

        clr(b,0); curL=i*len,curR=curL-1; pre=0;

        sort(V[i].begin(),V[i].end(),cmp);

        FOR0(j,SZ(V[i]))

        {

            x=V[i][j].L;

            y=V[i][j].R;

            k=V[i][j].id;

            ans[k]=pre;

            while(curR<y)

            {

                curR++;

                ans[k]-=C(b[a[curR]]);

                b[a[curR]]++;

                ans[k]+=C(b[a[curR]]);

            }

            while(curL<x)

            {

                ans[k]-=C(b[a[curL]]);

                b[a[curL]]--;

                ans[k]+=C(b[a[curL]]);

                curL++;

            }

            while(curL>x)

            {

                curL--;

                ans[k]-=C(b[a[curL]]);

                b[a[curL]]++;

                ans[k]+=C(b[a[curL]]);

            }

            pre=ans[k];

        }

    }

    u64 temp,p,q;

    FOR1(i,m)

    {

        p=ans[i];

        q=C(R[i]-L[i]+1);

        temp=Gcd(p,q);

        p/=temp; q/=temp;

        printf("%llu/%llu\n",p,q);

    }

}