题目描述
一个非负整数的序列，求长度满足某些条件的子区间的平均数的最大值，比如长度在$[L,R]$之间。
当然二分的解法就不讲了。
$O(N)$解法
先设原数组的前缀和数组是$S$，那么实际上就是寻找两个下标$i,j$，且满足$0 \le j<i \le N, L \le i-j \le R$，使得$\frac{S_i-S_j}{i-j}$最大，如果把下标$i$看作$X$坐标，$S_i$看作$Y$坐标，其实就是选两个符合条件的点，使得斜率最大。
注意到$S$单调不降，那我们就可以从前往后扫，对于每一个$i$，在它合法的区间$[i-R,i-L]$中，维护一个单调队列，其中队头到队尾（插入的地方）的点相对于点$i$单调递减（注意不是凸包），并且都是可能更新答案的点（注意并不是相对于$i$斜率最大的点）。对此就可以直接维护这个单调队列，延迟$L$插入，大于$R$的弹出并维护单调性即可。
另外需要说明的是为什么队头不是相对于$i$斜率最大的点，这是因为相对于$i$斜率最大的点可能在$i$之前就被某一个点从队尾弹出了，这是完全可能的，不懂的可以自己下来推，我只提供一组数据：
共五个点： $A(3,9),B(4,12),C(5,15),D(8,26),E(9,28),F(10,29)$
其中点$A,B,C$是合法区间的点，$D,E,F$是扫描到的点，$A$是$D$来时新增的点且排在了队头，$B$是$E$来时新增的点，$C$是$F$来时新增的点。
当$E$来时用$k_{EB}$弹掉了$k_{EA}$，$F$来时$k_{FC}$排在了$k_{FB}$之后，于是用$k_{FB}$更新答案，但实际上相对于$F$斜率最大的点是$A$，但用$k_{FA}$永远不可能更新答案，因为在处理$D$时的$k_{DA}$一定比$k_{FA}$优秀，同理后面的点相对于$A$也不可能比$k_{DA}$优秀。
