noip T4 一个很简单的做法

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

考虑根据 $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$；第三类同理，于是就做完了。