noip T4 一个很简单的做法

zhuzhu2891 · 2025-11-29 16:37:59 · 题解

令 p_i 表示前缀和数组。显然总共有四条限制：

• l\le i
• r>i
• r-l\ge L
• r-l\le R

考虑根据 r-i 是否 \le L 分成两部分。

对于 r-i\le L 的部分，第一条限制一定成立，所以用单调队列求出 f_r=p_r-\min_{r-R\le l\le r-L}p_l，然后再用用单调队列对 i 求出 \max_{i<r\le i+L}f_r 即可。

对于 r-i\ge L 的部分，第三条限制一定成立，令 d=R-L，此时相当于求出 \max_{l\in[i-d,i],r\in[i+L,i+L+d]}p_r-p_l，相当于二维平面上一个等腰直角三角形的部分。

考虑令 q_i=p_{i-L}，转化为对于每个 i 求 \max_{r-l\le d,l\le i\le r}q_r-p_l。我们每 d+1 个分一段，然后再把包含 i 的区间分成三类：端内，跨过这一段左端点，跨过这一段右端点的。

第一类的贡献就是后缀 \max 减前缀 \min；第二类发现这样的区间，覆盖的一定是 i 一段内的前缀，所以枚举 r，钦定跨过左端点后取后缀 \max；第三类同理，于是就做完了。