P1494 [CTT] Xiao Z's Socks

Updated on 2020.6.10: time limit updated. As a somewhat careless person, Xiao Z spends a long time every morning trying to find a pair of socks from a pile of colorful ones. One day, he could no longer stand this annoying process and decided to leave it to fate. Specifically, Xiao Z numbers his $N$ socks from $1$ to $N$, then randomly selects two socks to wear from those numbered $L$ to $R$. Although Xiao Z does not care whether the two socks form a true pair, he does care about their colors, since wearing two socks of different colors would be embarrassing. Your task is to tell Xiao Z the probability that he draws two socks of the same color. Of course, Xiao Z wants this probability to be as high as possible, so he may ask multiple queries $(L, R)$ to help him choose. However, there are cases with $L = R$ in the testdata. Please handle this case specially and output `0/1`.

The first line contains two positive integers $N$ and $M$. $N$ is the number of socks, and $M$ is the number of queries Xiao Z asks. The next line contains $N$ positive integers $C_i$, where $C_i$ denotes the color of the $i$-th sock; the same color is represented by the same integer. Then follow $M$ lines, each containing two positive integers $L, R$ representing a query.

Output $M$ lines. For each query, output a fraction $A/B$ on a single line representing the probability that two randomly chosen socks from the interval $[L, R]$ have the same color. If this probability is $0$, output `0/1`. Otherwise, $A/B$ must be in lowest terms (see the sample).

In $30\%$ of the testdata, $N, M \leq 5000$. In $60\%$ of the testdata, $N, M \leq 25000$. In $100\%$ of the testdata, $N, M \leq 50000$, $1 \leq L \leq R \leq N$, $C_i \leq N$. Translated by ChatGPT 5