分析
先考虑如果没有 (L) 和 (R) 的长度限制，我们发现最优解中对于区间 (lsim r)，(A_l) 和 (A_r) 应该分别为 (A_l,A_{l+1},cdots,A_r) 中的最大值和最小值。
考虑加上 (L) 和 (R) 的长度限制，若原来的区间为 (lsim r)，则会分如下 3 种情况进行讨论：
-
如果 (r-l+1< L)，那么我们可以考虑把它的长度补成 (L)。
-
如果 (Lle r-l+1le R)，那么这直接可以作为答案。
-
如果 (R<r-l+1)，那么它坏了。
综上所述，只有情况 (1,2) 是需要考虑的。
对于第一种情况
区间长度固定为 (L)，分 (A_r) 为最大值和最小值跑一下单调队列就好了。
对于第二中情况
我们再回来看那个式子，发现是个分数规划，非常常规地转换成判断性问题：
[egin{aligned}
frac{M(l,r)-m(l,r)}{r-l+K}&ge mid\
M(l,r)-m(l,r)&ge mid imes(r-l+K)\
M(l,r)-m(l,r)-mid imes r+mid imes l&ge mid imes K
end{aligned}
]
不妨另 (A_r) 为区间 (lsim r) 的最大值，(A_l) 为区间 (lsim r) 的最小值。
[egin{aligned}
A_r-A_l-mid imes r+mid imes l&ge mid imes K\
(A_r-mid imes r)-(A_l-mid imes l)&ge mid imes K
end{aligned}
]
用单调队列实现一下就可以了。
(A_r) 为区间 (lsim r) 的最小值，(A_l) 为区间 (lsim r) 的最大值同理。
实现细节
就是极为有用的小 trick——弱化最大值，最小值。
你会发现用上述方法实现非常困难，因为你要强制取最大或取最小。
但是稍作思考，你会发现，如果不取最大值最小值答案一定不会更优，所以写代码的时候完全不需要考虑。
#include<bits/stdc++.h>
#define log(a) cerr<<" 33[32m[DEBUG] "<<#a<<'='<<(a)<<" @ line "<<__LINE__<<" 33[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;
}