专栏文章

【解题报告】CF2042F Two Subarrays

SStarrykiller暁美 ほむら
CF2042F题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miqw5izf
此快照首次捕获于
2025/12/04 11:43
3 个月前
此快照最后确认于
2025/12/04 11:43
3 个月前
查看原文
显然的线段树。考虑如何合并信息，分类讨论一下发现只有几种情况：
  • 两个区间都在左侧/右侧。这个是好处理的。
  • 一个区间在左侧，另一个在右侧。这个也是好处理的。
  • 左侧有一个完整的区间，另外一个区间横跨左右。
  • 右侧有一个完整的区间，另外一个区间横跨左右。
发现只需要记录一个横跨的最大值方便拼接就可以了。于是，考虑维护以下信息：
  • answer\mathrm{answer}：区间内答案（即，两个不交子区间的最大权值和）。
  • mx\mathrm{mx}：区间内的最大权值（即，子区间的最大权值和）。
  • pre1\mathrm{pre1}：已经有了一个区间 [l,r][l,r]，剩下一个右边开口的区间 [l′,R][l',R]。
  • suf1\mathrm{suf1}：已经有了一个区间 [l,r][l,r]，剩下一个左边开口的区间 [L,r′][L,r']。
  • pre\mathrm{pre}：一个右边开口的区间 [l′,R][l',R]。
  • suf\mathrm{suf}：一个左边开口的区间 [L,r′][L,r']。
  • mid\mathrm{mid}：一个向左边开口的区间 [L,r′][L,r'] 和一个向右边开口的区间 [l′,R][l',R]。
  • suma\mathrm{suma}：区间内的 ∑ai\sum a_i。
然后直接转移即可。代码。时间复杂度 Θ((n+m)log⁡n)\Theta((n+m)\log n)。

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...