CF2042F 记录

· · 题解

注意，本文章中如果提到某个端点没有固定，那么在固定前默认延伸到本区间的末尾

考虑哪些信息需要维护

首先需要维护题目要求的答案 ans，而有以下几种情况：

  1. 两个答案区间在同一个子区间内，继承子区间答案就可以。
  2. 两个答案区间分别在不同子区间内，需要维护 ans2 代表单个答案区间的情况。
  3. 其中一个答案区间跨了中点，此时两种情况：
    1. 左答案区间跨中点。
    2. 右答案区间跨中点。

首先考虑 ans2，此时需要再维护两个值 premx,sufmx，分别代表左端点固定，右端点固定（另一个端点一直到区间结束）的最大值。

随后考虑情况 3，此时的两种形式：

  1. ....l1....mid....r1...l2....r2...
  2. ....l1....r1....l2....mid...r2...

考虑用 pre 代表左答案区间固定，右答案区间的右端点尚未存在的最大价值，suf 代表右答案区间固定，左答案区间的左端点尚未存在的最大价值。

### 坑点 本题我调了很久也没调出来，看了题解发现思路和题解完全一致。 我总算是查出了错，原因在于我在 SGT 的信息里使用了前缀和，但是我忘了 $a$ 数组的修改会改变一整个后缀的前缀和，导致 SGT 的信息出错。 ### 另外 以往我写线段树，通常只是将区间合并写死为树上左右子区间合并，而忽略了特殊情况下，查询的时候没法直接使用简单的加法乘法等操作将查询过程中找到的不同查询区间的子区间的答案合并，此时就需要使用 pushup 操作将它们逐个合并为整个查询的区间。 以后写线段树的时候需要注意这一点，防止类似情况再次被坑。