前言

这个乌克兰 OI 的题感觉都挺套路的。

思路

固定区间一端，随着区间另一端的扩展，gcd⁡\gcd 每次变化至少减半，最多变化 log⁡V\log V 次。因为求的是 [l,r][l,r] 内所有子区间的答案，考虑扫描线，钦定 ll 维护 rr。具体地，倒序枚举到 ll 时每次用 st 表倍增跳到以 ll 为左端点的区间 gcd⁡\gcd 变化的交界处 xx，然后对于 r>xr>x，ansr←max⁡(ansr,w∑i=lxai)ans_r\leftarrow \max(ans_r,w\sum\limits_{i=l}^xa_i)，其中 w=gcd⁡i=lxaiw=\gcd\limits_{i=l}^xa_i，ansrans_r 是区间 [l,r][l,r] 的答案。需要支持后缀取 max⁡\max 单点查询，树状数组即可。但是这样做会漏掉 rr 所在段的 gcd⁡\gcd 的贡献，因为这个时候我们虽然知道 gcd⁡\gcd 是多少，但却没办法维护区间和。因为 gcd⁡\gcd 一定时，我们想要区间和最大，所以解决方法是再独立算一遍 l≤l′≤r,r′=rl\leq l'\leq r,r'=r 的 [l′,r′][l',r'] 的答案。

这样做的复杂度是 O(nlog⁡nlog⁡V)\mathcal{O}(n\log n\log V)，而不是另一篇题解里的复杂度。只要固定了 xx，做 log⁡nlog⁡V\log n\log V 次将 xx 赋值为 gcd⁡(x,y)\gcd(x,y) 的操作的复杂度就是均摊 O(1)\mathcal{O}(1) 的，不需要 log⁡nlog⁡2V\log n\log^2V 次运算。