分析
先考虑如果没有 \(L\) 和 \(R\) 的长度限制，我们发现最优解中对于区间 \(l\sim r\)，\(A_l\) 和 \(A_r\) 应该分别为 \(A_l,A_{l+1},\cdots,A_r\) 中的最大值和最小值。
考虑加上 \(L\) 和 \(R\) 的长度限制，若原来的区间为 \(l\sim r\)，则会分如下 3 种情况进行讨论：
-
如果 \(r-l+1< L\)，那么我们可以考虑把它的长度补成 \(L\)。
-
如果 \(L\le r-l+1\le R\)，那么这直接可以作为答案。
-
如果 \(R<r-l+1\)，那么它坏了。
综上所述，只有情况 \(1,2\) 是需要考虑的。
对于第一种情况
区间长度固定为 \(L\)，分 \(A_r\) 为最大值和最小值跑一下单调队列就好了。
对于第二中情况
我们再回来看那个式子，发现是个分数规划，非常常规地转换成判断性问题：
\[\begin{aligned} \frac{M(l,r)-m(l,r)}{r-l+K}&\ge mid\\ M(l,r)-m(l,r)&\ge mid\times(r-l+K)\\ M(l,r)-m(l,r)-mid\times r+mid\times l&\ge mid\times K \end{aligned} \]不妨另 \(A_r\) 为区间 \(l\sim r\) 的最大值，\(A_l\) 为区间 \(l\sim r\) 的最小值。
\[\begin{aligned} A_r-A_l-mid\times r+mid\times l&\ge mid\times K\\ (A_r-mid\times r)-(A_l-mid\times l)&\ge mid\times K \end{aligned} \]用单调队列实现一下就可以了。
\(A_r\) 为区间 \(l\sim r\) 的最小值，\(A_l\) 为区间 \(l\sim r\) 的最大值同理。
实现细节
就是极为有用的小 trick——弱化最大值，最小值。
你会发现用上述方法实现非常困难，因为你要强制取最大或取最小。
但是稍作思考，你会发现，如果不取最大值最小值答案一定不会更优，所以写代码的时候完全不需要考虑。
#include<bits/stdc++.h>
#define log(a) cerr<<"\033[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<"\033[0m"<<endl
#define LL long long
#define SZ(x) ((int)x.size()-1)
#define ms(a,b) memset(a,b,sizeof a)
#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define DF(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
inline int read(){char ch=getchar(); int w=1,c=0;
for(;!isdigit(ch);ch=getchar()) if (ch=='-') w=-1;
for(;isdigit(ch);ch=getchar()) c=(c<<1)+(c<<3)+(ch^48);
return w*c;
}
const int N=5e4+10;
const double eps=1e-6;
int a[N],n,k,L,R,q[N],s,t;
double b[N],c[N];
inline double situation1(){
double ans=0;
s=1,t=0;
F(i,1,n){
while(s<=t&&i-q[s]>=L)s++;
if(s<=t)ans=max(ans,(a[i]-a[q[s]])/((double)(L+k-1)));
while(s<=t&&a[q[t]]>a[i])t--;
q[++t]=i;
}
s=1,t=0;
F(i,1,n){
while(s<=t&&i-q[s]>=L)s++;
if(s<=t)ans=max(ans,(a[q[s]]-a[i])/((double)(L+k-1)));
while(s<=t&&a[q[t]]<a[i])t--;
q[++t]=i;
}return ans;
}
inline bool check(double x){
F(i,1,n)b[i]=a[i]-x*i,c[i]=a[i]+x*i;
s=1,t=0;
F(i,1,n){
while(s<=t&&i-q[s]+1>R)s++;
if(s<=t&&b[i]-b[q[s]]>=x*k)return true;
if(i>=L){
while(s<=t&&b[q[t]]>b[i-L+1])t--;
q[++t]=i-L+1;
}
}
s=1,t=0;
F(i,1,n){
while(s<=t&&i-q[s]+1>R)s++;
if(s<=t&&c[q[s]]-c[i]>=x*k)return true;
if(i>=L){
while(s<=t&&c[q[t]]<c[i-L+1])t--;
q[++t]=i-L+1;
}
}
return false;
}
inline double situation2(){
double l=0,r=10001;
while(l+eps<r){
double mid=(l+r)/2.0;
if(check(mid))l=mid;
else r=mid;
}return l;
}
signed main(){
int _=read();
while(_--){
n=read(),k=read(),L=read(),R=read();
F(i,1,n)a[i]=read();
cout<<fixed<<setprecision(4)<<max(situation1(),situation2())<<endl;
}
return 0;
}