1 条题解

  • 0
    @ 2026-4-12 23:44:26

    核心转化

    设 (b_i = a_{i+1} - a_i),则:

    • (b_i > 0) 表示上升
    • (b_i < 0) 表示下降
    • (b_i = 0) 表示相等(破坏山峰)

    一个山峰在 (b) 数组上对应:一段连续正数后面紧接一段连续负数(中间没有0,也没有正负混插)。

    山峰宽度 = 正段长度 + 负段长度 + 1。


    区间加法的影响

    对 ([l, r]) 加 (d):

    • 只改变两个位置:(b_{l-1}) 增加 (d)(若 (l>1)),(b_r) 减少 (d)(若 (r<n))
    • 其他 (b) 不变。

    所以每次操作是 单点更新(最多两点)。


    维护方法

    用线段树维护 (b) 数组(长度 (n-1)),每个节点存:

    • 前缀最长连续正数长度
    • 后缀最长连续正数长度
    • 前缀最长连续负数长度
    • 后缀最长连续负数长度
    • 区间内最长正段+负段长度(即山峰宽度 - 1)

    合并时:

    • 左右子区间的最大长度取 max
    • 若左后缀正 + 右前缀负 → 可拼成新山峰
    • 若左后缀负 + 右前缀正 → 也可拼(对称情况)

    最后答案 = 根节点的最大值 + 1。


    复杂度

    • 单点更新 (O(\log n))
    • 查询 (O(1))(直接取根节点值)
    • 总复杂度 (O((n+m)\log n)),可过 3e5。
    • 1

    信息

    ID
    6208
    时间
    1000ms
    内存
    256MiB
    难度
    10
    标签
    递交数
    1
    已通过
    1
    上传者