根据小学我们就学过的一个简单公式,如果 $x = \prod p_i ^ { a_i } $ 那么 $x$ 因子个数为 $\prod a_i + 1$ 。因此我们需要维护查询的区间内每一个质数的和。

考虑把原来的数分解,这一步我们只需要预处理出小于 $ \sqrt { \max {a_i} }$ 的质数即可。然后对于每个数 $ a_i $ 依次判断小于 $ a_i $ 的质数。复杂度 $ O( \frac {n \sqrt{\max{a_i}}} {\log n} )$ ,实际情况下表现非常优越。或者采用 Pollard-Rho 算法优化为 $ n \times \sum { a_i^{ 1 / 4 } }$ ,但实现会较为复杂而且没有必要。

接下来考虑分解出的质数如何处理,如果直接放在一起去莫队的话复杂度是 $ O(n \sqrt n \log n) $ ,如果常数不优秀的话会 TLE 。我们考虑一个优化方式,对于大小在前 $\sqrt n$ 个的范围内的质数,预处理出个数,前缀和统计,不参与莫队,其余分解出的质数参与莫队,可以证明,每一个数需要参与莫队的数的个数是 $O(1)$ 级别的。这样的话复杂度降为 $n \sqrt n$ ,事实上我们可以把范围由 $\sqrt n$ 调整为 $100$ ~ $200$ 左右以获得一个较小的常数,跑到目前效率 rank 1。

bitset 套莫队板子题。

题意是如果第一个区间里有 $ a $ 个 $ x $ ,第二个区间 $ b $ 个,第三个区间 $ c $ 个,只会对答案产生 $ \min(a, b, c) $ 的贡献;每次询问给你三个区间,问你三个区间里能产生这样的贡献的大小。

考虑 bitset 套莫队。通过一个简单的 trick 使得 bitset 既能反映出每种数又能反映出每种数的个数,每个查询就用三个区间的 bitset 的按位并,取结果的 count 。

然而 $ 10^5 $ 个 $ 10^5 $ 的 bitset 会 MLE 。我们把莫队分成三次,只需要三分之一的空间,可以卡进。

看起来这样 $ O(n ^ 2) $ 的复杂度过不了 $ n = 10^5 $ ,但是由于使用了 bitset 的关系,常数只有 1 / 32 ,实际跑的飞快。

最近忽然发现 BZOJ 的权限题还是很多的(可能是因为以前搜不到就不搜了现在上 DARKBZOJ ),看来还是得众筹买个权限号了(雾

这是一道傻逼数据结构题,由于数据范围小,各种奇葩算法随便过。本菜鸡就写了个普通的树状数组套莫队,各位大佬不要见笑。

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×