这算的上是不带修改的莫队里边比较经典，也比较难的一道题了。

L=R的情况就不过多考虑了。

首先明确概率的计算方式，设总数为sum，其中数字a有C[a]种，那么a的几率就为C[a]/sum*(C[a]-1)/(sum-1).

要求化简为最简分数，那么我们可以先让所有数的几率都以sum*(sum-1)为底，那么我们现在只需要计算每种数字的 种类数*(种类数-1) 就可以了。

这题基本思想和 小B的询问 差不多，新加入或删除的数字，在答案中减去过去的贡献，加上现在所含的贡献。

例如：

序列中现已找到C[a]个a数，那么现在a这一类数对于答案的贡献为C[a]*(C[a]-1).那么如果再次加入一个a，那么则需要减掉C[a]*(C[a]-1)，加上C[a]*(C[a]+1),这个式子化简以下的话可以当做加上2*C[a],删除同理。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define N int(5e4+2)#define M int(5e4+2)#define LL long longusing namespace std;struct ahah{    LL L,R,p,f;}ask[N];struct haha{    LL math_numerator,math_denominator;    //分子,分母。 }ans[N];LL answer,n,m,q,a[N],cnt[N],k,_;LL gcd(LL a,LL b){  return !b?a:gcd(b,a%b); }bool comp(ahah a,ahah b){ return a.L/k==b.L/k?a.R
          
           
            0)answer+=(-2)*(cnt[a[pos]]);}void add(LL pos){ if(++cnt[a[pos]]>1)answer+=2*(cnt[a[pos]]-1); }void work(LL x,LL y,LL p){ if(!x)ans[p].math_numerator=0,ans[p].math_denominator=1; else { LL k=gcd(x,y); ans[p].math_numerator=x/k; ans[p].math_denominator=y/k; }}int main(){ scanf("%lld%lld",&n,&q); k=sqrt(n); for(int i=1;i<=n;i++)scanf("%lld",&a[i]); for(int i=1;i<=q;i++)scanf("%lld%lld",&ask[i].L,&ask[i].R),ask[i].p=i; sort(ask+1,ask+1+q,comp); LL curl=0,curr=0; //注意这里定义long long 不然下边会可能爆 for(int i=1;i<=q;i++) { LL L=ask[i].L,R=ask[i].R; if(L==R) { ans[ask[i].p].math_numerator=0; ans[ask[i].p].math_denominator=1; continue; } while(curl
            
             L)add(--curl); while(curr
             
              R)remove(curr--); work(answer,(R-L+1)*(R-L),ask[i].p); // <---- } for(int i=1;i<=q;i++)printf("%lld/%lld\n",ans[i].math_numerator,ans[i].math_denominator);}