【解题报告】CF2042F Two Subarrays

Starrykiller · 2024-12-03 19:55:48 · 题解

显然的线段树。考虑如何合并信息，分类讨论一下发现只有几种情况：

• 两个区间都在左侧/右侧。这个是好处理的。
• 一个区间在左侧，另一个在右侧。这个也是好处理的。
• 左侧有一个完整的区间，另外一个区间横跨左右。
• 右侧有一个完整的区间，另外一个区间横跨左右。

发现只需要记录一个横跨的最大值方便拼接就可以了。于是，考虑维护以下信息：

然后直接转移即可。代码。时间复杂度 \Theta((n+m)\log n)。