自动搬运

查看原文

来自洛谷，原作者为

	white_tiger_yyyy 少说话，多做事，自己和他人无关

搬运于2025-08-24 22:54:17，当前版本为作者最后更新于2024-01-17 17:37:47，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

博客食用更佳。

正篇开始

考虑题目中很重要的一句话：

• 记这 $k$ 个子序列中极差的最小值为 $X$，你需要求出 $X$ 的最大值。

很明显，要求最小值最大，显然二分答案。那么问题来了，二分什么呢？

现在有两个选择：二分极差、二分长度。

很明显，前者可以一次性都算出来，但是十分麻烦，无从下手；后者只能算出长度，但是二分思路很简单。这个时候，我们就需要发现一些性质了。

性质1：区间 $[l,r]$ 的子区间求出的极差绝对没有该区间大。

性质2：所有长度为 $l$ 的区间，都可以被长为 $l+1$ 的区间包含。

根据这两个性质，显而易见就可以推导出结论：

结论：区间长度越长，答案或更优，或不变。

这样，一个贪心求极差的方法显然出现：直接枚举所有长度为 $n-k+1$ 的区间，求出这些区间的极差最小值 $X'$，第一个答案即为 $X'$。

既然我们可以求出极差，那么我们就不需要二分极差，因此只能二分长度。但是问题接踵而至：如何快速计算区间极差呢？

解决这个问题，我们需要知道一件事情：区间极差=区间最大值-区间最小值。

问题转化为：如何快速求出静态区间最大/最小值？

用线段树自然可以，但是时间复杂度不如 RMQ。现在，我们只需要解决 $\operatorname{check}$ 函数即可。

$\operatorname{check}$ 函数的思路其实很普通。

二分长度，当该长度的区间中，有大于等于 $k$ 个大于 $X$，返回 $1$，否则返回 $0$。

现在我们会发现，使用线段树，时间复杂度会多一个 $\log$，而根据分析，原先的时间复杂度为 $O(n\log_2n)$，已经容不得 $n\log^2_2n$ 了。

空间复杂度最大是 RMQ，空间复杂度 $O(n\log_2n)$，最好预处理 $\log$。

标程

#include<bits/stdc++.h>
#define N 100005
#define M 1000005
using namespace std;
int t,n,k,a[N],mx[M],mn[N],ans1;
int lg[N],f[N][20],dp[N][20];
void build(){
    for(int i=1;i<=100000;i++)
        for(int j=1;j<17;j++) f[i][j]=-1e9-1;
    for(int i=1;i<=100000;i++)
        for(int j=1;j<17;j++) dp[i][j]=1e9+1;
    for(int i=1;i<=n;i++) f[i][0]=dp[i][0]=a[i];
    for(int j=1;j<17;j++)
        for(int i=1;i+(1<<j)-1<=n;i++){
            f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
            dp[i][j]=min(dp[i][j-1],dp[i+(1<<(j-1))][j-1]);
        }
}int qmax(int l,int r){
    int zjy=lg[r-l+1];
    return max(f[l][zjy],f[r-(1<<zjy)+1][zjy]);
}int qmin(int l,int r){
    int zjy=lg[r-l+1];
    return min(dp[l][zjy],dp[r-(1<<zjy)+1][zjy]);
}int check(int x){
    int sum=0;
    for(int i=1;i<=n-x+1;i++){
        int lyh=qmax(i,i+x-1);
        int zjy=qmin(i,i+x-1);
        if(lyh-zjy>=ans1) sum++;
    }return sum>=k;
}int main(){
    for(int i=1;i<N;i++) lg[i]=log2(i);
    cin>>t;while(t--){
        cin>>n>>k;ans1=2e9+1;
        for(int i=1;i<=n;i++) cin>>a[i];
        build();
        for(int i=1;i<=k;i++)
            ans1=min(ans1,qmax(i,n-k+i)-qmin(i,n-k+i));
        cout<<ans1<<" ";int l=1,r=n-k+1,ans2;
        while(l<=r){
            int mid=(l+r)/2;
            if(!check(mid)) l=mid+1;
            else r=mid-1,ans2=mid;
        }cout<<ans2<<"\n";
    }return 0;
}

赛后还有加强版，这会主要卡空间，所以无法支付 RMQ 的空间。

考虑单调队列。由于本题所需要的最大最小值，实际上是滑动窗口板子，所以可以将空间复杂度压缩至 $O(n)$。代码就不写了，留给大家探索。