题解

思路

把一个合法下标序列称为一条链。链中相邻两个位置严格递增，并且后一个位置上的值是前一个值的倍数。

对于询问 $[l,r]$，我们要统计起点和终点都位于该区间内的所有非空链。因为链的位置严格递增，只要起点不小于 $l$、终点不大于 $r$，整条链就一定完全位于 $[l,r]$ 中。

做法

子任务 1：逐询问动态规划

固定一个询问 $[l,r]$。令 $f_i$ 表示以位置 $i$ 结尾的合法链数，则

[ f_i=1+\sum_{l\le j<i,\ a_i\bmod a_j=0}f_j. ]

答案为 $\sum_{i=l}^r f_i$。

直接枚举 $i,j$，单个询问的时间复杂度为 $O((r-l+1)^2)$。在 $n,q\le 60$ 时足够通过。

子任务 2：严格递减排列

若 $a_i=n-i+1$，则位置越靠后，值越小。

排列中不存在相等元素，而一个更小的正整数不可能是前面更大正整数的倍数。因此不存在长度至少为 $2$ 的合法链，所有合法链都只含一个位置。

所以询问 $[l,r]$ 的答案就是

[ r-l+1. ]

满分算法

按链的起点离线

记 $pos_v$ 为值 $v$ 在排列中的位置。

从右向左枚举左边界 $L=n,n-1,\ldots,1$。在处理 $L$ 时，求出所有“第一个位置恰好为 $L$”的链，并按链的终点位置加入 Fenwick 树。

处理完 $L$ 后，Fenwick 树中保存的恰好是所有起点位置不小于 $L$ 的链。于是所有左端点为 $L$ 的询问 $[L,r]$，其答案就是 Fenwick 树在终点位置区间 $[L,r]$ 上的权值和。

计算固定起点的所有链

设 $x=a_L$。以 $L$ 为起点的链，其所有后续值都必须是 $x$ 的倍数。

令 $dp_v$ 表示当前已得到的、从位置 $L$ 开始并以值 $v$ 结束的链数。初始化

[ dp_x=1. ]

按值从小到大枚举 $x$ 的所有倍数 $y$。若 $pos_y<L$，则 $y$ 不可能出现在这条链中，跳过它。否则枚举 $y$ 的所有真倍数 $z$。当 $pos_z>pos_y$ 时，可以把所有以 $y$ 结束的链接上 $z$：

[ dp_z\mathrel{+}=dp_y. ]

数值严格增大，因此按数值从小到大处理就是合法的拓扑顺序，不会漏掉更长的整除链。

最后，对于 $x$ 的每个倍数 $y$，把 $dp_y$ 加到 Fenwick 树的 $pos_y$ 位置，并清空该临时状态，供下一个起点复用。

标准程序采用完全等价的反向写法：先翻转排列和询问，再从左向右扫描右端点。两种写法统计的是同一组“起点—终点”链。

正确性证明

处理左边界 $L$ 时，$dp_x=1$ 对应只包含位置 $L$ 的链。

假设所有以某个值 $y$ 结束的链已经被正确计入 $dp_y$。对每个满足 $y\mid z$ 且 $pos_z>pos_y$ 的值 $z$，把 $z$ 接到这些链后得到的序列仍满足位置递增和相邻整除，因此转移产生的每条链都合法。

反过来，任意长度至少为 $2$、从 $L$ 开始并以 $z$ 结束的合法链，都有唯一的倒数第二个值 $y$。它满足 $y\mid z$ 且 $pos_y<pos_z$，所以这条链会在从 $y$ 到 $z$ 的转移中被计入。由归纳可知，所有从 $L$ 开始的链都被恰好统计一次。

从右向左处理到 $L$ 后，Fenwick 树中包含所有且仅包含起点不小于 $L$ 的链。查询终点位置区间 $[L,r]$，便得到所有起点、终点均位于 $[L,r]$ 的链，也就是询问答案。

复杂度

整除枚举的总转移次数为 $O(n\log^2 n)$。每个“起点值—终点值”的整除对进行一次 Fenwick 树更新，总复杂度同样为 $O(n\log^2 n)$。每个询问需要 $O(\log n)$。

因此每个测试文件的总时间复杂度为

[ O(n\log^2 n+q\log n), ]

空间复杂度为 $O(n+q)$。