0x40数据结构进阶（0x44 分块）例题4：P1494 [国家集训队] 小 Z 的袜子

P1494 [国家集训队] 小 Z 的袜子

【题意】

$n$ 个数的序列 $a_i$，有 $m$ 次操作。每次操作询问区间 $[l,r]$ 随机选两个数相同的概率。

【输入格式】

一行两个整数 $n,m$。

下来 $n$ 个正整数 $a_i$。

下来 $m$ 行，每行两个整数 $l,r$，表示询问的区间。

$1\le n,m,a_i \leq 5 \times 10^4$，$1\le l \le r \le n$

【输出格式】

$m$ 行，每个询问在一行中输出分数 $A/B$ 表示从该询问的区间 $[l,r]$ 中随机选两个数相同的概率。

若该概率为 $0$ 则输出 0/1，否则输出的 $A/B$ 必须为最简分数。

【样例输入】

6 4
1 2 3 3 3 2
2 6
1 3
3 5
1 6

【样例输出】

2/5
0/1
1/1
4/15