P12484

rehtam · 2026-03-04 20:30:12 · 题解

一个略微爆标的做法，时间复杂度 O(n \log n)。

快进到分治之后计算答案增量，不妨令修改的位置在左区间中。对左区间每个位置 i 维护一个值 p 表示最大的 pos 满足 \displaystyle \max_{mid+1}^{pos} < a_i，右区间同理。则一次修改对右区间 p 值的影响是全局取 max，对左区间的影响是弹栈。只需维护一个 tag 并在弹栈时下放 tag 即可。计算贡献时再用一个栈维护 p 值等于 v 的端点个数。