ZOJ 4029 - Now Loading!!!

题面

现有 nn 个整数 a1,a2,,ana_1, a_2, \dots, a_n,并且有 mm 次查询。每次查询时需对给定的 pp 计算下面表达式的值:

1inailogpai\sum\limits_{1 \le i \le n}\Bigl\lfloor \frac{a_i}{\lceil\log_{p}a_i\rceil}\Bigr\rfloor

数据范围

1n,m5×1051 \le n, m \le 5 \times 10^5

2ai,pi1092 \le a_i, p_i \le 10^9

题目链接

分析

我们注意到,logpai\lceil\log_{p}a_i\rceil 的取值在题目的取值范围下其实非常有限:

logpai[1,31]\lceil\log_{p}a_i\rceil \in [1, 31]

也就是说,对于同一个 pplogpai\lceil\log_{p}a_i\rceil 的值很可能对于多个 aia_i 是相等的。

另外我们注意到 logpai\log_{p}a_i 是单调递增的。如果我们先对这 nn 个整数从小到大排序,那么对于排序后的数列,我们可以将其划分为若干个连续区间,使得每个区间内 logpai\lceil\log_{p}a_i\rceil 的值都相等。那么我们不妨将排序后的数组连续地划分成 3131 个区间(区间可以包含 00 个元素),使得每个区间内所有 aia_ilogpai\lceil\log_{p}a_i\rceil 都相等。如果我们能够快速地求出每个区间的区间和加起来,这样复杂度就能降低不少。

既然 logpai\lceil\log_{p}a_i\rceil 的取值情况很少,我们可以考虑预处理所有的 aik (kZ,k[1,31])\frac{a_i}{k} \ (k \in \mathbb{Z}, k \in [1, 31])。同时在预处理的时候,我们可以将其处理为前缀和的形式,这样我们就可以以 O(1)\mathcal{O}(1) 的复杂度求出上面提到的每个区间的区间和。

至于区间具体如何划分,我们不妨借助二分查找。第 kk 个区间的第一个元素也就是原数组中第一个大于 pkp^k 的元素。

这样一来,预处理的复杂度为 O(n)\mathcal{O}(n)mm 次查询的复杂度为 O(mlogn)\mathcal{O}(m\log{n}),而常数则为 3131

实现

完整参考代码

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/05/01/zoj-4029/