题解：CF1946F Nobody is needed

毒瘤卡常，来写题解了。

设计 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$ 的增加量（第二次差分），我们发现：