BZOJ2038 [2009國家集訓隊]小Z的襪子(hose) 莫隊

Description

作為一個生活散漫的人，小Z每天早上都要耗費很久從一堆五顔六色的襪子中找出一雙來穿。終于有一天，小Z再也無法忍受這惱人的找襪子過程，于是他決定聽天由命……

具體來說，小Z把這N隻襪子從1到N編号，然後從編号L到R(L 盡管小Z并不在意兩隻襪子是不是完整的一雙，甚至不在意兩隻襪子是否一左一右，他卻很在意襪子的顔色，畢竟穿兩隻不同色的襪子會很尴尬。

你的任務便是告訴小Z，他有多大的機率抽到兩隻顔色相同的襪子。當然，小Z希望這個機率盡量高，是以他可能會詢問多個(L,R)以友善自己選擇。

Input

輸入檔案第一行包含兩個正整數N和M。N為襪子的數量，M為小Z所提的詢問的數量。接下來一行包含N個正整數Ci，其中Ci表示第i隻襪子的顔色，相同的顔色用相同的數字表示。再接下來M行，每行兩個正整數L，R表示一個詢問。

Output

包含M行，對于每個詢問在一行中輸出分數A/B表示從該詢問的區間[L,R]中随機抽出兩隻襪子顔色相同的機率。若該機率為0則輸出0/1，否則輸出的A/B必須為最簡分數。（詳見樣例）

Sample Input

6 4

1 2 3 3 3 2

2 6

1 3

3 5

1 6

Sample Output

2/5

0/1

1/1

4/15

【樣例解釋】

詢問1：共C(5,2)=10種可能，其中抽出兩個2有1種可能，抽出兩個3有3種可能，機率為(1+3)/10=4/10=2/5。

詢問2：共C(3,2)=3種可能，無法抽到顔色相同的襪子，機率為0/3=0/1。

詢問3：共C(3,2)=3種可能，均為抽出兩個3，機率為3/3=1/1。

注：上述C(a, b)表示組合數，組合數C(a, b)等價于在a個不同的物品中選取b個的選取方案數。

【資料規模和約定】

30%的資料中 N,M ≤ 5000；

60%的資料中 N,M ≤ 25000；

100%的資料中 N,M ≤ 50000，1 ≤ L < R ≤ N，Ci ≤ N。

HINT

Source

是莫隊的一道好題。

下次把莫隊好好講講（上一篇好像說過了。，額。。）

這題其實還需要計算一下點對的總數來計算機率。

其實就是一個數的出現次數t：t*(t-1)/2

那麼在莫隊裡就可以改寫了。詳細的統計方法可以看我的程式裡面的add（加入）和remove（移除）

對于答案分子分母還需要化簡。

那麼就用一個gcd（最大公約數）的方法來化簡吧。

對了！！

仔細估計一下最大情況，50000*50000是要超出2^31的！

這意味着我們需要開long long。。。$_$

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int
  NM=50005,
  block=225; //√50000
int n,m,a[NM];
ll ans,App[NM];
struct Query{
  int l,r,id;
}Q[NM];
struct Answer{
  ll fz,fm; //fenzi fenmu
}Ans[NM];
inline int read(){
  int x=0,f=1;char ch=getchar();
  while (ch<'0' || ch>'9'){if (ch=='-') f=-1;ch=getchar();}
  while (ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
  return x*f;
}
bool cmp(Query x,Query y){
  if (((x.l-1)/block+1)!=((y.l-1)/block+1))
    return x.l<y.l;
  return x.r<y.r;
}
inline void add(int x){
  ans+=App[a[x]];
  App[a[x]]++;
}
inline void remove(int x){
  App[a[x]]--;
  ans-=App[a[x]];
}
ll gcd(ll a,ll b){
  if (!b) return a;
    else  return gcd(b,a%b);
}
int main(){
  n=read(),m=read();
  for (int i=1;i<=n;i++)
    a[i]=read();
  for (int i=1;i<=m;i++)
    Q[i].l=read(),Q[i].r=read(),Q[i].id=i;
  sort(Q+1,Q+1+m,cmp);
  int L=1,R=1; add(1);
  ans=0;
  for (int i=1;i<=m;i++){
    while (L<Q[i].l) remove(L++);
    while (L>Q[i].l) add(--L);
    while (R<Q[i].r) add(++R);
    while (R>Q[i].r) remove(R--);
    ll t=(ll)(((ll)(Q[i].r-Q[i].l+1))*((ll)(Q[i].r-Q[i].l))/(ll)2);
    ll tt=gcd(t,ans);
    Ans[Q[i].id].fz=ans/tt;
    Ans[Q[i].id].fm=t/tt;
  }
  for (int i=1;i<=m;i++)
    printf("%lld/%lld\n",Ans[i].fz,Ans[i].fm);
  return 0;
}