F. 无人需要 详细题解

题目核心理解

给定一个长度为 $n$ 的排列 $a$，以及 $q$ 个询问。 每个询问给出区间 $[l,r]$，求满足以下条件的下标递增序列数量：

1. 所有下标 $t_i$ 都满足 $l\le t_i\le r$；
2. 下标严格递增：$t_1<t_2<\dots<t_k$；
3. 后一个位置上的数能被前一个整除：$a_{t_{i+1}}\bmod a_{t_i}=0$；
4. 序列长度至少为 $1$。

---

核心思路

1. 关键性质

• 因为是排列，每个数值唯一，可以用 $\text{pos}[v]$ 表示数值 $v$ 出现的位置。
• 答案具有可加性，可以按左端点从大到小离线处理询问。
• 用树状数组维护：以每个位置结尾、起点 $\ge L$ 的合法序列数量。
• 转移只发生在倍数之间，总转移次数为 $O(n\log^2n)$。

2. DP 定义与转移

设：

• $\text{dp}[i]$：起点为当前左端点 $L$，终点为 $i$ 的合法序列条数。
• 初始：$\text{dp}[L]=1$（单独一个位置本身就是合法序列）。

转移规则： 对当前位置的值 $v=a[L]$，枚举它的所有倍数 $y$， 如果 $\text{pos}[y]$ 在 $L$ 右侧，则

$$\text{dp}[\text{pos}[y]]\ += \text{dp}[L]$$

3. 统计答案

树状数组维护所有 $\text{dp}[i]$， 询问 $[l,r]$ 的答案就是树状数组上

$$\sum_{i=l}^{r} \text{dp}[i]$$

---

算法流程

1. 读入排列，预处理每个数值的位置 $\text{pos}[v]$。
2. 将所有询问按左端点从大到小排序，实现离线处理。
3. 从 $n$ 到 $1$ 倒序枚举左端点 $L$：
   • 初始化 $\text{dp}[L]=1$。
   • 枚举 $a[L]$ 的所有倍数，更新对应位置的 $\text{dp}$ 值。
   • 将 $\text{dp}$ 值更新到树状数组中。
4. 对所有左端点为 $L$ 的询问，查询树状数组区间 $[L,r]$ 的和作为答案。
5. 按原询问顺序输出结果。

---

公式与复杂度分析

转移公式：

$$\text{dp}[\text{pos}[y]]\ += \text{dp}[\text{pos}[x]] \quad(y \text{ 是 } x \text{ 的倍数},\ \text{pos}[y]>\text{pos}[x]) $$

单次询问答案：

$$ans(l,r)=\sum_{i=l}^{r} \text{dp}[i]$$

复杂度

• 预处理倍数：$O(n\log n)$
• DP 转移：$O(n\log^2 n)$
• 询问处理：$O(q\log n)$
• 总体：$O(n\log^2 n+q\log n)$

可轻松处理 $n,q\le 10^6$、多组数据总和限制。