[bzoj2648]小$Z$的袜子——普通莫队

题目大意

给出一个有$n$个数的数列$A:a_1,a_2,a_3\dots a_n$，询问$m$次

每次询问给出一个区间$[l,r]$，询问区间$[l,r]$内抽到一对数值相等的数的概率大小

数据范围

$n,m\leqslant 50000$，$1\leqslant l< r\leqslant n$，$a_i\leqslant n$

题解

不妨设区间$[l,r]$里元素个数为$len$，显然，抽一对数的情况总数为$C_{len}^2$

同时区间里只有$k$种数值，每种数值对应的元素有$s_1,s_2\dots s_k$个，抽一对数值相等的数的情况总数为$C_{s_1}^2+C_{s_2}^2+\dots C_{s_k}^2$

则答案为$$\frac{C_{s_1}^2+C_{s_2}^2+\dots C_{s_k}^2}{C_{len}^2}=\frac{s_1(s_1-1)+s_2(s_2-1)+\dots s_k(s_k-1)}{len(len-1)}=\frac{s_1^2+s_2^2+\dots s_k^2-len}{len(len-1)}$$

那么现在问题简化为，如何即时地统计所有的$s_1,s_2\dots s_k$

这个时候引入一个东西，莫队算法，是莫涛前几年提出的算法，适用于解决离线区间查询问题

Question Ⅰ：这个算法怎么用啊？

假设已经得到了区间$[l,r]$需要统计的信息，可以在常数级别的时间内转移到区间$[l-1,r]$、区间$[l+1,r]$、区间$[l,r-1]$、区间$[l,r+1]$

那么可以在$O(n\sqrt n)$的时间复杂度求得所有答案

Question Ⅱ：这个时间复杂度？

我们可以调整一下处理每个查询的顺序，保证最优的顺序之下转移区间

将$n$个数分成$\sqrt n$块

按区间排序，以左端点所在块内为第一关键字，右端点为第二关键字，进行排序

然后按这个排序直接暴力，复杂度分析是这样的：

1. $i$与$i+1$在同一块内，$r$单调递增，所以$r$是$O(n)$的，由于有$\sqrt n$块，所以这一部分时间复杂度是$n\sqrt n$

2. $i$与$i+1$跨越一块，$r$最多变化$n$，由于有$\sqrt n$块，所以这一部分时间复杂度是$n\sqrt n$

3. $i$与$i+1$在同一块内，$l$变化不超过$\sqrt n$，跨越一块也不会超过$\sqrt n \times 2$

由于有$m$次询问（和$n$同级），所以时间复杂度是$n\sqrt n$

阅读更多……

题目大意

给出一个数列$A:a_1,a_2,a_3 \cdots a_n$

执行$m$次询问，每次给出区间$[l,r]$

在$[a_l,a_r]$中选一个数$x$

在$[a_1,a_{l-1}]$或者$[a_{r+1},a_n]$中选一个数$y$

求$gcd(x,y)$最大

阅读更多……