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。
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 200005;
int n, m, h, l, r, a[maxn], N, c[maxn];
struct point
{
int l, r, id, a, b;
bool operator <(const point&a) const
{
if (l / N == a.l / N) return r < a.r;
else return l / N < a.l / N;
}
}p[maxn];
bool cmp(const point&a, const point&b)
{
return a.id < b.id;
}
int get(int l, int r)
{
long long ans = r - l + 1;
ans = ans*(ans - 1) >> 1;
return (int)ans;
}
int gcd(int x, int y)
{
if (x%y) return gcd(y, x%y);
return y;
}
void getgcd(int &x, int &y)
{
if (!x) { y = 1; return; }
int z = gcd(x, y);
x /= z; y /= z;
}
void solve()
{
for (int i = 1, l = 1, r = 0; i <= m; i++)
{
p[i].a = p[i - 1].a;
for (; l < p[i].l; l++) p[i].a -= --c[a[l]];
for (; l > p[i].l;) p[i].a += c[a[--l]]++;
for (; r < p[i].r;) p[i].a += c[a[++r]]++;
for (; r > p[i].r; r--) p[i].a -= --c[a[r]];
}
}
int main()
{
while (scanf("%d%d", &n, &m) != EOF)
{
N = sqrt(n);
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
p[0].l = p[0].r = p[0].a = p[0].id = 0;
for (int i = 1; i <= m; i++)
{
scanf("%d%d", &p[i].l, &p[i].r);
p[i].id = i; p[i].a = 0; p[i].b = get(p[i].l, p[i].r);
}
sort(p + 1, p + m + 1);
solve();
sort(p + 1, p + m + 1, cmp);
for (int i = 1; i <= m; i++)
{
getgcd(p[i].a, p[i].b);
printf("%d/%d\n", p[i].a, p[i].b);
}
}
return 0;
}