化简式子
$M>=m+ans*(r-l+k)$
发现$M,m$确定时，总区间长度越小越好，于是假定右端点为最小值$M+ans*l>=m+ans*r+ans*k$,
右面都确定了，但最大值仍然有两种情况，一是最大值就在要求的区间内，二是在要求的区间右侧，
对于第一种情况，直接把每个点的val扔进单调队列就可以了，第二种呢，因为要求区间长度最小，所以左端点即为$r-L+1$，单调队列维护$i-L+1~i$的最大值即可，
左端点为最小值也一样。
而且不需要判断在我们选的区间内是否有比$a[i]$更小的，因为那一定比这优，考虑过，
所以每次check直接正反扫就好了。
2017.11.7更新
原程序被hack,因为如果只能全选的话，最小值又不在两边，就不会枚举到最优解，所以强行往两侧各添加n个0即可。
代码已更正，可放心食用
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#define N 150050
#define eps 1e-6
using namespace std;
int n,l,r,k;
int a[N];
double val[N];
int q1[N],q2[N],head1,head2,tail1,tail2;
bool check(double x){
head1=head2=;
tail1=tail2=;
for(int i=;i<=*n;i++){
int pos=i-l+;
double now=-;
if(pos>){
val[pos]=a[pos]+x*pos;
while(head1<=tail1&&val[pos]>val[q1[tail1]])tail1--;
q1[++tail1]=pos;
while(head1<=tail1&&q1[head1]<=i-r)head1++;
now=max(now,val[q1[head1]]);
}
while(head2<=tail2&&a[i]>a[q2[tail2]])tail2--;
q2[++tail2]=i;
while(head2<=tail2&&q2[head2]<=i-l)head2++;
if(i>n&&pos>){
now=max(now,a[q2[head2]]+x*(i-l+));
if(now>=a[i]+x*(i+k))return ;
}
}
head1=head2=;
tail1=tail2=;
for(int i=*n;i>=n+;i--){
int pos=i+l-;
double now=-;
if(pos<=*n){
val[pos]=a[pos]-x*pos;
while(head1<=tail1&&val[pos]>val[q1[tail1]])tail1--;
q1[++tail1]=pos;
while(head1<=tail1&&q1[head1]>=i+r)head1++;
now=max(now,val[q1[head1]]);
}
while(head2<=tail2&&a[i]>a[q2[tail2]])tail2--;
q2[++tail2]=i;
while(head2<=tail2&&q2[head2]>=i+l)head2++;
if(i<=*n&&pos<=*n){
now=max(now,a[q2[head2]]-x*(i+l-));
if(now>=a[i]-x*(i-k))return ;
}
}
return ;
}
int main(){
int T;scanf("%d",&T);
while(T--){
scanf("%d%d%d%d",&n,&k,&l,&r);
for(int i=n+;i<=*n;i++)scanf("%d",&a[i]);
double L=,R=,M;
while(L+eps<R){
M=(L+R)/2.0;
if(check(M))L=M;
else R=M;
}
printf("%0.4lf\n",M);
}
return ;
}
bzoj4476