长乐集训 - NOI模拟赛（三十三）「订正未完成」
没交
$\text{score：NULL rk：NULL}$
Problem A：区间第k小
题面
题解
先考虑离线，整体二分，二分答案 $mid$，处理所有 $\le mid$ 的数，那么此时问题就转化为在区间出现次数不超过 $w$ 的数有多少个
不妨关注每个数对询问区间 $[L, R]$ 的贡献，对某个数 $a$，若它是从左往右后 $w$ 个出现为 $a$ 的数，则它的贡献为 $1$，若为倒数第 $w + 1$ 个则贡献为 $- w$，剩下的贡献都为 $0$，那么我们就可以开一个队列，首先总大小（即不删去超过 $w$ 的）算出来，此时计算需要删去的，队列大小未到 $w$ 时没有需要删的，若大于 $w$ 时每次就让队首点贡献减去 $w + 1$，当然之前多减的还要加回来
那么现在就可以考虑从离线转成在线，在整体二分的过程中每一层（即每一次二分的 $[l, r]$）都会建一些可持久化线段树，而它又最多会修改 $O (n \log n)$ 次，开 $O (n \log^2 n)$ 个节点，所以把每一层的可持久化线段树都存下来，在线二分时即可直接查找，总时间复杂度 $O (n \log^2 n)$
代码
1 |
|
Problem B：求和
题面
题解
首先对式子进行变换
$$
\begin{aligned}
ans &= \sum\limits_{i = 1}^n\sum\limits_{j = 1}^n\sum\limits_{d = 1}^k f_d(gcd(i, j)) \\
&= \sum\limits_{x = 1}^n\sum\limits_{d = 1}^k f_d(x)\sum\limits_{i = 1}^{\lfloor\frac{n}{x}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{n}{x}\rfloor}[(i, j) = 1] \\
&= \sum\limits_{x = 1}^n\sum\limits_{d = 1}^k f_d(x)\left((2\sum\limits_{i = 1}^{\lfloor\frac{n}{x}\rfloor}\varphi(i)) - 1\right)
\end{aligned}
$$
那么这时对 $n$ 整除分块到，$\sum\limits_{i = 1}^n \varphi(i)$ 就可以直接杜教筛求出，设此时分块到 $[l, r]$，现在考虑求解 $\sum\limits_{x = l}^r\sum\limits_{d = 1}^k f_d(x)$，当然前缀和是肯定的
令 $F_d(x) = \sum\limits_{i = 1}^n f_d(i)$，设质因数分解 $n = \prod\limits_i p_i^{c_i}$，令 $\lambda(x) = \prod\limits_i (- 1)^{c_i}$，$F_d(x)$ 则可以通过容斥求出
$$
\begin{aligned}
F_d(x) &= \sum\limits_{i = 1}^x \mu(i)\sum\limits_{j = 1}^{\lfloor\frac{x}{i^{d + 1}}\rfloor}\lambda(i^{d + 1}j) \\
&= \sum\limits_{i = 1}^x \lambda^{d + 1}(i)\mu(i)\sum\limits_{j = 1}^{\lfloor\frac{x}{i^{d + 1}}\rfloor}\lambda(j)
\end{aligned}
$$
第一步实际上就是类似求 $n$ 以内无平方因子数的方法，$i = 1$ 时为总方案，后面容斥删去不合法
而第二步是因为 $\lambda(x)$ 是一个完全积性函数
现在问题转化为求 $\sum\limits_{i = 1}^n \lambda(i)$，可以发现一个性质，$\sum\limits_{d |n} \lambda(i) = [n为完全平方数]$
下面给出证明
- 设 $n = \prod\limits_i p_i^{c_i}$，考虑两个数 $p_1^2x, p_1^3x$，满足 $p_1^2x, p_1^3x | n$，若 $p_1^2x$ 的贡献为 $1$，那么 $p_1^3x$ 的贡献则一定为 $- 1$，那么以此类推，也就是 $0, 1$ 次、$2, 3$ 次、$4, 5$ 次…分别两两配对，若 $c_i$ 为奇数，则最后贡献总和一定为 $0$，若为偶数，最后则一定为 $1$
这样的话就是 $\sqrt n = \lambda * 1$，就可以杜教筛了
那么对 $F_d(x)$，类似杜教筛预处理 $x$ 比较小的（注意用原式，即 $F_d(x) = \sum\limits_{i = 1}^n f_d(i)$ 来预处理），然后大的就直接暴力枚举，最多 $O (\sqrt n)$，那么这样总时间复杂度是 $O (n^{\frac23})$ 的
代码
1 |
|