化简式子
$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即可。
代码已更正，可放心食用
1 #include2 #include 3 #include 4 #include 5 #include 6 #define N 150050 7 #define eps 1e-6 8 using namespace std; 9 int n,l,r,k;10 int a[N];11 double val[N];12 int q1[N],q2[N],head1,head2,tail1,tail2;13 bool check(double x){14 head1=head2=1;15 tail1=tail2=0;16 for(int i=1;i<=2*n;i++){17 int pos=i-l+1;18 double now=-1000000000;19 if(pos>0){20 val[pos]=a[pos]+x*pos;21 while(head1<=tail1&&val[pos]>val[q1[tail1]])tail1--;22 q1[++tail1]=pos;23 while(head1<=tail1&&q1[head1]<=i-r)head1++;24 now=max(now,val[q1[head1]]);25 }26 while(head2<=tail2&&a[i]>a[q2[tail2]])tail2--;27 q2[++tail2]=i;28 while(head2<=tail2&&q2[head2]<=i-l)head2++;29 if(i>n&&pos>0){30 now=max(now,a[q2[head2]]+x*(i-l+1));31 if(now>=a[i]+x*(i+k))return 1;32 }33 }34 head1=head2=1;35 tail1=tail2=0;36 for(int i=3*n;i>=n+1;i--){37 int pos=i+l-1;38 double now=-1000000000;39 if(pos<=3*n){40 val[pos]=a[pos]-x*pos;41 while(head1<=tail1&&val[pos]>val[q1[tail1]])tail1--;42 q1[++tail1]=pos;43 while(head1<=tail1&&q1[head1]>=i+r)head1++;44 now=max(now,val[q1[head1]]);45 }46 while(head2<=tail2&&a[i]>a[q2[tail2]])tail2--;47 q2[++tail2]=i;48 while(head2<=tail2&&q2[head2]>=i+l)head2++;49 if(i<=2*n&&pos<=3*n){50 now=max(now,a[q2[head2]]-x*(i+l-1));51 if(now>=a[i]-x*(i-k))return 1;52 }53 }54 return 0;55 }56 int main(){57 int T;scanf("%d",&T);58 while(T--){59 scanf("%d%d%d%d",&n,&k,&l,&r);60 for(int i=n+1;i<=2*n;i++)scanf("%d",&a[i]);61 double L=0,R=1000,M;62 while(L+eps