题意
有两道菜，做第一道菜有 \(n\) 个步骤，完成第 \(i\) 步需要 \(a_i\) 分钟，做第二道菜有 \(m\) 个步骤，完成第 \(j\) 步需要 \(b_j\) 分钟。两道菜的步骤可以交替执行，中途不能休息。
若你在 \(s_i\) 分钟内完成第一道菜的第 \(i\) 步，则获得 \(p_i\) 分。若你在 \(t_j\) 分钟内完成第二道菜的第 \(j\) 步，则获得 \(q_j\) 分。求做完两道菜后的最大得分。
\(1\leq n,m\leq 10^6\)，\(1\leq a_i,b_j\leq 10^9\)，\(1\leq s_i,t_j\leq 2\times 10^{15}\)，\(|p_i|,|q_j|\leq 10^9\)。
题解
对 \(a,b\) 做前缀和，容易得到一个 \(\mathcal{O}(nm)\) 的 DP：令 \(f_{i,j}\) 表示第一道菜做了前 \(i\) 步，第二道菜做了前 \(j\) 步，能获得的最大的分。转移枚举最后一步做的是哪一道菜：
预处理 \(c_i\) 表示最大的 \(j\) 使得 \(b_j\leq s_i-a_i\)，\(d_j\) 表示最大的 \(i\) 使得 \(a_i\leq t_j-b_j\)。自然地放到平面上考虑，将所有 \((i,c_i)\) 和 \((d_j,j)\) 标为关键点。考虑一条从 \((0,0)\) 到 \((n,m)\) 的路径，发现问题可以转化成：若点 \((i,c_i)\) 在路径的上方（非严格）则可以获得 \(p_i\) 分，若点 \((d_j,j)\) 在路径的下方（非严格）则可以获得 \(q_j\) 分，最大化得分。如下图所示。
考虑统一一下方向，先令答案为 \(\sum p_i\)，那么变成若点 \((i,c_i)\) 在路径的下方（严格）则可以获得 \(-p_i\) 分，然后将 \((d_j,j)\) 向右下移动变为 \((d_j+1,j-1)\)。问题转化成最大化路径下方（严格）的点权。
考虑此时的 DP：令 \(f_{i,j}\) 表示从 \((0,0)\) 走到 \((i,j)\)，路径下方的最大点权和。设 \(w_{i,j}\) 为 \((i,j)\) 处的点权总和，\(S_{i,j}=\sum\limits_{k=0}^{j-1}w_{i,k}\) 为 \((i,j)\) 下方的点权总和。转移在向右走时累加下方点权和：
注意由于一些点向右下方移动了一个单位，最终答案应为 \(f_{n,m}+S_{n+1,m}\)。
DP 的转移变得比较优美了，考虑整体 DP 优化。我们将 \(i\) 这一维压掉，那么转移相当于先对于每个 \(1\leq j\leq m\)，令 \(f_j\gets f_j+S_{i,j}\)，再对 \(f\) 做一次前缀 \(\max\)。考虑维护差分数组 \(g_j=f_j-f_{j-1}\)，此时第一步操作变为对于每个 \(1\leq j\leq m\)，令 \(g_j\gets g_j+w_{i,j-1}\)，而 \(w_{i,j}\) 有值的位置只有 \(\mathcal{O}(n+m)\) 个，这很不错。
考察取前缀最大值的过程在差分数组上的表现。依次考虑 \(f\) 的每个前缀最大值 \(f_{p_1}\leq\cdots\leq f_{p_k}\)：将 \(g_{p_1+1\sim p_2-1}\) 置为 \(0\)，令 \(g_{p_2}\gets \sum\limits_{k=p_1+1}^{p_2}g_k\)，将 \(g_{p_2+1\sim p_3-1}\) 置为 \(0\)……可以发现这个过程等价于令 \(t=p_{i}+1,sum=0\)，不断执行以下操作：
- 令 \(sum\gets sum+g_t\)。
- 若 \(sum\geq 0\)，则令 \(g_t\gets sum\)，停止操作。
- 否则令 \(g_t\gets 0\)，\(t\gets t+1\)。
用 map 维护 \(g\) 的非 \(0\) 项，每次在 \(x\) 的位置单点操作后，从该位置开始向后执行上述操作即可。显然除了最后一个位置，被遍历的位置都会被删除，时间复杂度为 \(\mathcal{O}((n+m)\log(n+m))\)。