T1 可以用悬线法达到 O(n),就是维护 f[i] 表示区间 [L[i], i] 的最大值,L[i] 转移时 f[i] = max(f[i], f[L[i] - 1]),同样维护 g[i] 表示 [i, R[i]] 的最大值,最后 f[i] 和 g[i] 取 max 就可以求区间最大值了,提交记录https://ac.nowcoder.com/acm/contest/view-submission?submissionId=64234962

相关推荐

10-30 22:18
已编辑
毛坦厂中学 C++
点赞 评论 收藏
分享
牛客网
牛客企业服务