题解：P14523 【MX-S11-T4】Ice Drop

SegTree · 2025-11-17 20:28:23 · 题解

考虑如何计算 f(b) 如何计算：

• 若删去序列中的 1 时不是好的，则 f(b)=0；
• 否则对于每个质因子分别计算。对于一个 1 段方案数容易用插板法计算。

考虑维护序列 t_i 表示 f(a_{i,\cdots,r})。

先求出 nxt_i 表示最大的 r 满足 a_{i,\cdots,r} 合法，然后相当于在 nxt_i+1 处做单点置 0，在 i 处单点置 1。描述其它的操作，令 p 表示上一个满足 a_p\ne 1 的位置。

然后求区间历史和。a_i=1 乘上的要撤销。

时间复杂度 O(n(\log V+\log n)+q\log n)。