题解：CF1946F Nobody is needed

LinkCatTree · 2025-07-23 19:23:42 · 题解

毒瘤卡常，来写题解了。

设计 dp 状态 f_{l, r} 表示区间 [l, r] 中整除序列的个数，可知 dp 转移为 f_{l, r}=\sum_{l \leq k < r} [a_k | a_r] f_{l, k}，这样朴素 dp 的时间复杂度是 \mathcal{O}(qn^2) 的，卡常都过不了。而我们发现转移的 dp 状态第一维都是相同的，自然想到滚动第一维 l。

于是我们运用常用技巧，从 n 到 1 枚举 l，对 l 分组进行离线查询，我们可以运用线段树或者树状数组之类的做到 \mathcal{O}(\log n) 单次询问。考虑从以 n 到 1 的顺序枚举 l，我们希望可以以较优的时间复杂度将以 l+1 为左端点时的 f_{l+1 \cdots n} 转移为以 l 为左端点时的 f_{l \cdots n}。

此时 dp 转移上无法较显然的进一步优化，我们挖掘题目性质。我们发现由于加入了 a_l 产生了以 a_l 为第一个的整除序列使 f 值改变：假设一个整除序列为 a_l, \cdots, a_r，则 f_{r \cdots n} \leftarrow f_{r \cdots n} + 1。若我们对 f 进行差分得到 h，那么该整除序列相当于使 h_r \leftarrow h_r + 1。而由于 a_l | \cdots | a_r 即 a_r 为 a_l 的倍数，我们发现：对于排列 a，至多只有不超过 \dfrac n{a_l} 个 h_i 会改变，而且每个 a_l 均摊仅会使 \mathcal{O}(\log n) 个 h_i 改变！

于是我们再维护一个 g_i 来表示每次 h_i 的增加量（第二次差分），我们发现：

由于非零的 g 较少，于是我们可以 \mathcal{O}(\log^2 n) 枚举 g_i 和 g_j 进行转移。处理出 g 值后，使用线段树进行 \mathcal{O}(\log n) 次 \mathcal{O}(\log n) 的修改操作，再维护 \sum \sum g_i \mathcal{O}(\log n) 查询，总时间复杂度 \mathcal{O}(n \log^2 n+q \log n)，不卡常不能过（也有可能是因为我程序天生常数大）。

接下来是一点奇怪的优化？卡常？

1. 用树状数组而非线段树，我不信有人能写线段树过了这题（

2. 预处理加入 a_l 时会有哪些 h_i 会变化，即提前枚举并存储好在 a_l 右侧的 a_l 的倍数。

代码仅供参考并安利博客：here。