【题解】
1,先说说莫队算法。
莫队算法是用来离线处理区间问题的算法。非常易于理解和使用,且运用十分广泛。
假设我们现在已知区间[L,R]的答案,如果我们能以较低的时间复杂度扩展得到区间$[L-1,R],[L+1,R],[L,R-1],[L,R+1]$的答案,我们就可以使用莫队算法。通常可以接受的扩展的时间复杂度为$O(1)$或者$O(logN)$.
那么莫队算法具体是怎样的呢?首先我们把询问按照区间左端点分成$\sqrt{n}$块,同一块内按照区间右端点进行排序。当我们按调整后的顺序处理询问时,如果左端点比询问区间的左端点小,那就把左端点右移,如果左端点比询问区间的右端点大,那就把左端点左移;右端点也同理。然后再把处理好的询问按原来的顺序储存。
为什么这样做可以保证时间复杂度?假设扩展的时间复杂度为$f(n)$,区间长为$n$,询问次数为$m$。显然,对于每次询问,左端点最多移动$\sqrt{n}$次,那么移动左端点的总时间复杂度就是$O(f(n)*\sqrt{n}*m)$;右端点移动次数与询问次数无关,即在同一个块内,右端点最多移动n次,那么移动右端点的时间复杂度就是$O(f(n)*\sqrt{n}*n)$. $m$和$n$同阶,那么莫队算法的时间复杂度就是$O(f(n)*\sqrt{n}*n)$.
还有一个常数优化,就是当块的编号为奇数时,把询问按照区间右端点从小到大排序;当块的编号为偶数时,把询问按照区间右端点从大到小排序。这样可以减少右端点移动的次数。实测可以有效提高效率。
2,本题是莫队算法的基础题。假设共有n只袜子,每种颜色的袜子的数量是cnt[i],选中同色袜子的概率是$Sigma(0.5*cnt[i]*(cnt[i]-1))/(0.5*n*(n-1))$.