看到极差，不难想到双指针。
显然，如果 \([l,r]\) 的位置都被覆盖，那么其中最多可以选 \(\lceil\frac{r-l+1}{2}\rceil\) 个数。
我们先将所有数离散化，排序，双指针卡取值范围。
set 里面存 pair 类型变量，表示覆盖的区间。
每次将值为 \(r\) 的数的位置加入，在 set 中二分到与它相邻的区间，然后减去贡献，合并区间，加上新的贡献。
删除同理，将区间拆分，减去原先贡献，加上新的贡献即可。
复杂度 \(O(n\log n)\)。
代码有点长，但思路很清晰。
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fir first
#define sec second
#define mkp make_pair
using namespace std;
const int N=1e5+5;
int n,m,a[N],tmp[N],cnt;
vector<int>v[N];
set<pii >st;
int get(int l,int r){
return (r-l+2)/2;
}
void ins(int w){
set<pii >::iterator it2=st.lower_bound(mkp(w,0)),it=it2;
int fl=0,fr=0;
if(it2!=st.begin()){
--it;
if((*it).sec==w-1)fl=1;
}if(it2!=st.end()&&(*it2).fir==w+1)fr=1;
if(!fl&&!fr)++cnt,st.insert(mkp(w,w));
else if(!fl&&fr){
int r=(*it2).sec;
if((r-w)%2==0)++cnt;
st.erase(it2);
st.insert(mkp(w,r));
}else if(fl&&!fr){
int l=(*it).fir;
if((w-l)%2==0)++cnt;
st.erase(it);
st.insert(mkp(l,w));
}else{
int l=(*it).fir,r=(*it2).sec;
cnt-=get(l,w-1)+get(w+1,r)-get(l,r);
st.erase(it);st.erase(it2);st.insert(mkp(l,r));
}
}
void del(int w){
set<pii >::iterator it=st.upper_bound(mkp(w,1e9+1));--it;
int l=(*it).fir,r=(*it).sec;
if(w==r){
cnt-=get(l,r)-get(l,r-1);
st.erase(it);
if(l<r)st.insert(mkp(l,r-1));
}else if(w==l){
cnt-=get(l,r)-get(l+1,r);
st.erase(it);st.insert(mkp(l+1,r));
}else{
cnt-=get(l,r)-get(l,w-1)-get(w+1,r);
st.erase(it);st.insert(mkp(l,w-1));st.insert(mkp(w+1,r));
}
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;++i){
cin>>a[i];
tmp[i]=a[i];
}
sort(tmp+1,tmp+n+1);
int p=unique(tmp+1,tmp+n+1)-(tmp+1);
for(int i=1;i<=n;++i)a[i]=lower_bound(tmp+1,tmp+p+1,a[i])-tmp,v[a[i]].push_back(i);
int l=1,r=0,ans=1e9;
while(1){
while(cnt<m&&r<p){
++r;
for(int i=0;i<v[r].size();++i)ins(v[r][i]);
}
if(cnt<m)break;
ans=min(ans,tmp[r]-tmp[l]);
for(int i=0;i<v[l].size();++i)del(v[l][i]);
++l;
}
cout<<ans<<endl;
return 0;
}