作为一个生活散漫的人小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。
终于有一天小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命
具體来说,小Z把这N只袜子从1到N编号然后从编号L到R的袜子中随机选出两只来穿。
尽管小Z并不在意两只袜子是不是完整的一双甚至不在意两呮袜子是否一左一右,他却很在意袜子的颜色毕竟穿两只不同色的袜子会很尴尬。
你的任务便是告诉小Z他有多大的概率抽到两只颜色楿同的袜子。
当然小Z希望这个概率尽量高,所以他可能会询问多个(L,R)以方便自己选择
第一行包含两个正整数N和M,N为袜子的数量M为小Z所提的询问的数量。
接下来一行包含N个正整数CiCi其中CiCi表示第i只袜子的颜色,相同的颜色用相同的数字表示
再接下来M行,每行两个正整数LR表示一个询问。
包含M行对于每个询问在一行中输出分数A/B表示从该询问的区间[L,R]中随机抽出两只袜子颜色相同的概率。
若该概率为0则输出0/1否则输出的A/B必须为最简分数。
题解:本题求区间[L,R]中随机抽出两只袜子颜色相同的概率相当于求区间相同元素数量。我们可以用莫队来做先对“询问”进行分块,这是一种离线算法:先把所有要询问的区间读入然后根据左端点所在块排序(分成√n块),再按右端点排序为什么左端点要按块排序而不直接排序呢?如果先按左端点从小到大排序再按右端点从小到大排序的话左端点的移动是单调的,但右端点的变化不能确定左端点按块排序再排右端点的话,相邻两个询问左端点的变化在√n范围内右端点单调。这样显然更优然后我们萣义两个指针,一个指向左端点L一个指向右端点R,两个指针根据询问的区间移动并不断更新L~R区间中各个元素的数量,同时更新题目所求的随机抽出两只袜子颜色相同的情况数每个区间记完数量后除以这个区间随机选两只袜子的情况数再约分就是个、本题答案。