【bzoj2724】[Violet 6]蒲公英

2014年7月6日3,6813

Description

 

Input

修正一下

l = (l_0 + x – 1) mod n + 1, r = (r_0 + x – 1) mod n + 1

Output

HINT

修正下:

n <= 40000, m <= 50000

题解

在线区间众数的分块做法比较多,这里提供一个思路:

首先离散化一下比较方便。

最初可能会有一个想法,是不是众数只可能是完整的块的众数,或者不完整的块出现的数呢?显然很容易得出反例。

应该是完整的所有块的众数,和不完整块中出现的数。

所以我们可以预处理f(i,j)表示第 i 块到第 j 块的众数(枚举 i 开个桶扫一遍)。

那么只要能快速得出一个数在某个区间内出现次数即可,每次只要比较至多2√n+1个元素的出现次数,这题就解决了。

由于没有修改,只要离散化以后,给每个数 x 开个vector,按顺序存下 x 出现的位置,每次询问 x 时把区间的左右端点放进对应 vector 二分一下即可。

根据均值不等式,可以算出分块大小大概是√(n/logn)