【题意】给定n个数字ai，每次询问一个区间中随机抽选两个数字，数字相同的概率，以分数最简形式输出。n,ai<=50000。

【算法】莫队算法

【题解】参考： by 

使用莫队算法的关键在于维护区间信息的增减。

对于区间[L,R]，令其中数字i的出现次数为xi，则ans=[ ΣC(xi,2) ] / [ C(Σxi,2) ]。

化简可得，ans=Σx^2-(r-l+1)/C(r-l+1,2)

维护A数组表示每个数字出现次数，每次区间移动一格：减，变，加。

异块按左坐标排序，同块按右坐标排序。

莫队别忘了分块。

优化：

1.奇偶分块：根据块编号的奇偶性，奇数块内r升序，偶数块内r降序。

2.块大小：block=n/sqrt(m*2/3)。

#include
      
       #include
       
        #include
        
         #include
         
          #define ll long longusing namespace std;int read(){    int s=0,t=1;char c;    while(!isdigit(c=getchar()))if(c=='-')t=-1;    do{s=s*10+c-'0';}while(isdigit(c=getchar()));    return s*t;}const int maxn=50010;int n,m,a[maxn],be[maxn],block;ll c[maxn],sum,ansA[maxn],ansB[maxn];struct cyc{
    int l,r,id;}b[maxn];bool cmp(cyc a,cyc b){
    return be[a.l]^be[b.l]?a.l
          
           
            b.r);}ll gcd(ll a,ll b){ return !b?a:gcd(b,a%b);}void modify(int x,int p){ //printf("%d %d\n",x,p); sum-=c[a[x]]*c[a[x]]; c[a[x]]+=p; sum+=c[a[x]]*c[a[x]];} int main(){ n=read();m=read(); for(int i=1;i<=n;i++)a[i]=read(); block=(int)(1.0*n/sqrt(1.0*m*2/3)); for(int i=1;i<=n;i++)be[i]=(i-1)/block+1; for(int i=1;i<=m;i++)b[i].l=read(),b[i].r=read(),b[i].id=i; sort(b+1,b+m+1,cmp); int L=1,R=0; sum=0;// for(int i=1;i<=m;i++){ for(int j=L-1;j>=b[i].l;j--)modify(j,1); for(int j=R+1;j<=b[i].r;j++)modify(j,1); for(int j=L;j<=b[i].l-1;j++)modify(j,-1); for(int j=R;j>=b[i].r+1;j--)modify(j,-1); ll A=sum-(b[i].r-b[i].l+1),B=1ll*(b[i].r-b[i].l+1)*(b[i].r-b[i].l); ll g=gcd(A,B); ansA[b[i].id]=A/g;ansB[b[i].id]=B/g; L=b[i].l;R=b[i].r; } for(int i=1;i<=m;i++)printf("%lld/%lld\n",ansA[i],ansB[i]); return 0;}