P15066 [UOI 2024 II Stage] GCD, Sum, Multiply. What?... 题解

M1rai · 2026-01-26 23:33:34 · 题解

前言

更可爱的阅读体验

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

思路

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

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