小z的袜子

题目描述
作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……

具体来说,小Z把这 $N$ 只袜子从 $1$ 到 $N$ 编号,然后从编号 $L$ 到 $R$ 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。

你的任务便是告诉小Z,他有多大的概率抽到两只颜色相同的袜子。当然,小Z希望这个概率尽量高,所以他可能会询问多个$(L,R)$以方便自己选择。

然而数据中有$L=R$的情况,请特判这种情况,输出$0/1$。

输入文件第一行包含两个正整数 $N$ 和 $M$ 。$N$为袜子的数量,$M$ 为小Z所提的询问的数量。接下来一行包含 $N$ 个正整数 $C_i$,其中 $C_i$ 表示第 $i$ 只袜子的颜色,相同的颜色用相同的数字表示。再接下来 $M$ 行,每行两个正整数 $L,R$ 表示一个询问。

输出包含 $M$ 行,对于每个询问在一行中输出分数 $A/B$ 表示从该询问的区间 $[L,R]$ 中随机抽出两只袜子颜色相同的概率。若该概率为 $0$ 则输出 $0/1$ ,否则输出的 $A/B$ 必须为最简分数。

$N,M \le 50000, 1 \le L < R \le N, Ci \le N$

代码
讲一下实现原理:
令询问区间为 $S$, $cnt[i]$ 表示颜色为 $i$ 的袜子在 $S$ 内出现的次数, 那么就有
$$ans = \frac {\sum{C_{cnt[i]}{2}}}{C_{S.len}{2}}$$
把分母拎出来
$$\frac {S.len!}{2!(S.len - 2)!} = \frac{1}{2}(S.len - 1)\times S.len = \frac{1}{2}(S.len^2 - S.len)$$
同理,分子可以化简为
$$\frac{1}{2}(cnt[1]^2 - cnt[1] + cnt[2]^2 - cnt[2]+ … + cnt[x]^2 - cnt[x])$$
$$\frac{1}{2}(cnt[1]^2 + cnt[2]^2 + … + cnt[x]^2 - S.len)$$
上下两式相除把 $\frac{1}{2}$ 抵消掉
$$ans = \frac {\sum{cnt[i]^2} - S.len}{S.len^2 - S.len}$$
然后就按照询问的左右端点分块排序,暴力处理即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//最近想试试压行的感觉
//没开LL爆掉了...

int precmp(const ASK&a, const ASK&b){
return P[a.l] == P[b.l] ? a.r < b.r : a.l < b.l;
}//把询问按照第一关键字左端点第二关键字右端点所在的块排序

int aftcmp(const ASK&a, const ASK&b){ return a.id < b.id;}

void change(int col, int key){
ans -= cnt[col]*cnt[col];
cnt[col] += key;
ans += cnt[col]*cnt[col];
//最朴素的处理方法反而很难想到呢
}

void deal(){
it_l = 1, it_r = 1;
++ cnt[num[1]], ans = 1;
//这里我一开始把左右指针都放在1的位置,所以相应的,cnt[num[1]]和ans都要初始化
for(int i = 1; i <= m; ++ i){
L = ask[i].l, R = ask[i].r;
while(it_l < L) change(num[it_l ++], -1);
while(it_l > L) change(num[-- it_l], 1);
while(it_r < R) change(num[++ it_r], 1);
while(it_r > R) change(num[it_r --], -1);
//真的是暴力处理了啊
if(L == R){
ask[i].son = 0, ask[i].ma = 1;
continue;
}
//特别注意对于L=R时的处理
//如果选择在最开始就直接跳过它,要考虑是否会对之后的计算产生影响
//不过这里是没有影响的..
len = R - L + 1;
ask[i].son = ans - len, ask[i].ma = (LL)len * (len - 1);
k = gcd(ask[i].son, ask[i].ma);
ask[i].son /= k, ask[i].ma /= k;
}
}

int main(){
n = read(), m = read(), siz = (int)sqrt(n);
for(int i = 1; i <= n; ++ i) num[i] = read(), P[i] = i/siz;
for(int i = 1; i <= m; ++ i) ask[i].l = read(), ask[i].r = read(), ask[i].id = i;
sort(ask + 1, ask + m + 1, precmp);
deal();
sort(ask + 1, ask + m + 1, aftcmp);//排回去
for(int i = 1; i <= m; ++ i) printf("%lld/%lld\n", ask[i].son, ask[i].ma);
return 0;
}