P13544 [OOI 2022] Serious Business
题目
Dima 参加了好友 Peter 举办的节目《Peter 帮兄弟找工作》。在这个节目中，Dima 需要穿越一个 \(3 \times n\) 的矩形场地，场地共有 \(3\) 行 \(n\) 列。每行的格子从左到右编号为 \(1\) 到 \(n\)。
每个格子 \((i, j)\) 内有一个整数 \(a_{i, j}\)。Dima 的初始分数为 \(0\)，每当他经过某个格子 \((i, j)\)，分数会增加 \(a_{i, j}\)（分数可能为负）。
起初，第一行和第三行的所有格子都是可用的，第二行所有格子都是不可用的。但 Peter 为 Dima 提供了 \(q\) 个特殊帮助，第 \(i\) 个特殊帮助可以将第二行的第 \(l_i\) 列到第 \(r_i\) 列的格子标记为可用，但每次使用该特殊帮助，Dima 的分数会减少 \(k_i\)。Dima 可以任意多次使用这些特殊帮助，同一格子可被多次解锁。
Dima 从第一行第一列的格子 \((1, 1)\) 出发，目标是到达第三行最后一列的格子 \((3, n)\)。每次他可以向下走到下一行，或者向右走到下一列（即行号或列号加 \(1\)），因此总共需要 \(n+1\) 步，其中 \(n-1\) 步为向右，\(2\) 步为向下。
Peter 承诺根据 Dima 的最终分数付费，最终分数为经过的所有格子的分数之和减去使用所有特殊帮助的总花费。请你帮助 Dima 最大化他的最终分数。
（\(1 \le n, q \le 500\,000\)）
思路
暴力做法即枚举第二行的区间，贪心覆盖，复杂度 \(O(n^2)\) 。
考虑dp。设 \(f_i\) 表示从 \((1,1)\) 到 \((2,r_i)\) 的最大分数。
若在当前区间内的点 \(j,l_i\le j\le r_i\) 为第一层拐点，则有 \(f_i=\max s1_j+s2_{r_i}-s2_{j-1}-k_i\) ，令 \(a_j=s1_j-s2_{j-1}\) ，即为 \(a_j\) 的区间最大值。
若拐点在当前区间外，则可以从前面的区间转移过来，有 \(f_i=\max f_j+s2_{r_i}-s2_{r_j}-k_i\) ，令 \(a_{r_j}=f_j-s2_{r_j}\) ，即为 \(a_j\) 的区间最大值。
考虑记录答案。最初的想法是找到第二层拐点的区间在右端点 \(r\) 前，回溯贡献 ，然而会出现这样的情况：
即第一拐点在第二拐点后的情况。这样显然不合法。然而在记录状态时 \(f_i\) 只记录了右端点最右位置，并不知道第一个拐点是从哪里来。
这样回溯就可能造成不合法。可以按照上面的做法，枚举第二拐点所在的最右区间，再次将情况分为两种。
第一种，第一拐点与第二拐点在同一区间 \(i\) 上，有 \(ans=\max s1_j+s2_k-s2_{j-1}+s3_n-s3_{k-1}-k_i=\max ((s1_j-s2_{j-1})+(s2_k-s2_{k-1})+s3_n-k_i)\) 。
第二种，从上一个区间转移过来，则有 \(ans=max f_{r_j}+s2_k-s2_{r_j}+s3_n-s3_{k-1}-k_i=max((f_{r_j}-s2_{r_j})+max(s2_k-s3_{k-1})+s3_n-k_i)\) 。
注意到，这两种转移都是 \(\max A(x)+B(y)，l\le x\le y\le r\) 的形式，容易用线段树维护。
时间复杂度 \(O(n\log n)\) 。