听睡神说此题是一道分数规划题，虽然我并不知道分数规划是什么东东
，反正好像是二分一下答案，然后将分母乘过去，然后再去解决。
首先易知当长度大于L小于等于R的时候，最大值和最小值一定在边界最优。然后等于L的情况特判一下就好了。
所以，先二分答案x，然后用RMQ处理长度为L的特殊情况。之后我们分两种情况。
①i为最大值，j为最小值。所以只要找到这样一对(i,j)(L<j-i+1<=R)，(a[i]-a[j])/(j-i+K)>=x说明x是可行的，我们把分母乘过去，
a[i]-a[j]>=x*j-x*i+x*K
=>a[i]+x*i-(a[j]+x*j)>=x*K
所以我们只要令b[i]=a[i]+x*i，然后维护一个单调队列即可。
②i为最小值，j为最大值。与上相同，但此时的式子是
a[j]-a[i]/(j-i+K)>=x
=>a[j]-a[i]>=x*j-x*i+x*K
=>a[j]-x*j-(a[i]-x*i)>=x*K
此时我们只要令b[i]=a[i]-x*i，再维护一下单调队列就好了。
因此，我们以nlogn的复杂度完美解决了本题。
#include<cstdio>
#include<algorithm>
using namespace std;
typedef double db;
struct node{int id;double x;}q[50010];
int T,n,K,L,R;
int a[50010],Max[50010][25],Min[50010][25],len[50010];
double eps=1e-6,b[50010];
int ask(int x,int y){int j=len[y-x+1];return max(Max[x][j],Max[y-(1<<j)+1][j])-min(Min[x][j],Min[y-(1<<j)+1][j]);}
bool judge(db x)
{
int p1,p2;
for (int i=1;i<=n;i++)
if (i+L-1>n) break;else
if ((db)ask(i,i+L-1)>=(L-1+K)*x) return true;
p1=1,p2=0;
for (int i=1;i<=n;i++)
b[i]=(db)(a[i]-i*x);
for (int i=L+1;i<=n;i++)
{
while (p1<=p2&&(i-q[p1].id+1>R)) p1++;
while (p1<=p2&&q[p2].x>=b[i-L]) p2--;
q[++p2].id=i-L;
q[p2].x=b[i-L];
if (b[i]-b[q[p1].id]>=x*K) return true;
}
for (int i=1;i<=n;i++)
b[i]=(db)(a[i]+i*x);
p1=1,p2=0;
for (int i=L+1;i<=n;i++)
{
while (p1<=p2&&(i-q[p1].id+1>R)) p1++;
while (p1<=p2&&q[p2].x<=b[i-L]) p2--;
q[++p2].id=i-L;
q[p2].x=b[i-L];
if (b[q[p1].id]-b[i]>=x*K) return true;
}
return false;
}
void binary(db l,db r)
{
if (r-l<=eps){printf("%.4lf\n",l);return;}
db mid=(l+r)/2;
if (judge(mid)) binary(mid,r);else binary(l,mid);
}
int main()
{
for (int i=1;i<=50000;i++)
for (int j=20;j>=0;j--)
if ((1<<j)<=i){len[i]=j;break;}
scanf("%d",&T);
while (T--)
{
scanf("%d%d%d%d",&n,&K,&L,&R);
for (int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
Min[i][0]=a[i];
Max[i][0]=a[i];
}
for (int j=1;j<=20;j++)
for (int i=1;i<=n;i++)
if (i+(1<<j)-1>n) break;else
{
Max[i][j]=max(Max[i][j-1],Max[i+(1<<(j-1))][j-1]);
Min[i][j]=min(Min[i][j-1],Min[i+(1<<(j-1))][j-1]);
}
binary(0,1000);
}
}
