【题解】P7009

· · 题解

对于一个值域为 V 的序列，他后缀 \gcd 中不同的值只有 O(\log V) 个，因为每次加入一个数，\gcd 要么不变，要么至少减半。那么就很简单了。我们设现在考虑右端点为 x 时的答案。那么我们维护序列 a_1, \ldots a_x 后缀 \gcd 每一个连续段的左端点，我们开一个链表，每一个节点存一个二元组 (i, j)，分别表示这个位置的下标和目前为止的后缀 \gcd。我们首先遍历链表，使 j \gets \gcd(j, a_x)，然后把重复元素删掉，最后加入二元组 (x, a_x)，并更新答案。时间复杂度 O(n\log V)。Code