AC. 梦想

frank_c1

[BZOJ 2038] 小Z的袜子

发布于2016年02月18日 | 暂无评论 | 2,414阅读 | 莫队算法

题目描述

作为一个生活散漫的人,小Z每天早上都要耗费很久从一堆五颜六色的袜子中找出一双来穿。终于有一天,小Z再也无法忍受这恼人的找袜子过程,于是他决定听天由命……
具体来说,小Z把这N只袜子从1到N编号,然后从编号L到R(L 尽管小Z并不在意两只袜子是不是完整的一双,甚至不在意两只袜子是否一左一右,他却很在意袜子的颜色,毕竟穿两只不同色的袜子会很尴尬。

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

输入格式

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

输出格式

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

题目解析

如果采用线段树、平衡树数据结构来维护,会发现非常难以实现。这时我们考虑采用一些其他的算法。

莫队算法适用于允许离线,没有修改的区间询问问题。前提是,如果知道区间[L,R]的答案,能较快得到[L-1,R][L+1,R][L,R-1][L,R+1]的答案。据说可以用平面曼哈顿最小生成树实现对询问的合理排序,从而保证复杂度。但是感觉还是分块的性价比比较高一点,理论上说用平面曼哈顿最小生成树和分块实现的莫队复杂度是同阶的。

分块的具体实现如下:记pos(l)l所在块的编号,对所有询问以pos(l)为第一关键字,r为第二关键字进行排序。设本次询问区间为[L,R],上次询问区间为[L',R'],则可以在|L-L'|+|R-R'|的时间实现答案的转移。

下面从整体上分析算法的复杂度。由于算法仅涉及L和R的变化,所以L和R的总变化量就可以反映算法的复杂度。

1.左端点L:块内 - 根据排序的原则,两次询问间块内L变化不会超过O(\sqrt n),询问n次,故复杂度为O(n \sqrt n);块际 - 块际间L变化O(\sqrt n),由于只有O(\sqrt n)块,故复杂度为O(n)

2.右端点R:块内 - 因为同一块内R递增,每一块内R变化O(n),共O(\sqrt n)块,故复杂度为O(n \sqrt n);块际 - 块际间R变化O(n),由于只有O(\sqrt n)块,故复杂度为O(n \sqrt n)

综上所述,算法的整体复杂度为O(n \sqrt n)