1 条题解
-
0
核心转化
设 (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
- 上传者