题目意思：
需要在元素互不相同的数列 \(a\) 中选出一个长度为 \(m\) 的元素互不相邻的子列，使得子列的极差最小。
做法
我们知道，对于一组数列，我们只需知道它的最大值和最小值，就可以得到它的极差。那么我们可以将数字从小到大排序，固定最小值，寻找最优的最大值，当最小值和最大值的位置固定了，那么我们要选出的数定在最小值和最大值位置的范围内。
我们从小到大枚举最小值，容易发现最大值在已排序序列中的位置是有单调性的。便再用一个指针去枚举最大值。用线段树维护这个区间所有数的位置，对于一段连续位置的数字，最优的选取方案就是它的长度除以二（向上取整），那么整个贡献便是每段数字贡献之和。时间复杂度为 \(O(NlogN)\)。
#include<bits/stdc++.h>
#define N 100005
#define ll long long
using namespace std;
ll n,m,res,ans=99999999999999;
struct xs{ll x,k;}a[N];
struct ys{
ll l,r,sum,lsum,rs,rsum,ls,fla;
//l表示区间内最左边可选数字的位置，r类似，表示最右边
//lsum表示区间内最左边可选数字的所在段中最多能选的数字个数，lsum类似，表示最右边
//rs表示区间内最左边可选数字的所在段中的右端点，ls类似，表示最右边的左端点
//fla表示整个区间是否有且仅有一段可选数字，sum表示整个区间最多能选的数字个数
}tr[N*4];
bool cmp(xs x,xs y){return x.x<y.x;}
void pushup(ll rt){
if(tr[rt<<1].sum&&tr[rt<<1|1].sum){
tr[rt].l=tr[rt<<1].l,tr[rt].r=tr[rt<<1|1].r;
tr[rt].lsum=tr[rt<<1].lsum,tr[rt].rs=tr[rt<<1].rs,tr[rt].rsum=tr[rt<<1|1].rsum,tr[rt].ls=tr[rt<<1|1].ls;
if(tr[rt<<1].r==tr[rt<<1|1].l-1){
if(tr[rt<<1].fla==1&&tr[rt<<1|1].fla==1){
tr[rt].sum=tr[rt].lsum=tr[rt].rsum=(tr[rt<<1|1].r-tr[rt<<1].l+2)/2;
tr[rt].fla=1,tr[rt].ls=tr[rt<<1].l,tr[rt].rs=tr[rt<<1|1].r;
}else{
tr[rt].sum=tr[rt<<1].sum-tr[rt<<1].rsum+tr[rt<<1|1].sum-tr[rt<<1|1].lsum+(tr[rt<<1|1].rs-tr[rt<<1].ls+2)/2;
tr[rt].fla=0;
if(tr[rt<<1].fla){
tr[rt].lsum=(tr[rt<<1|1].rs-tr[rt<<1].l+2)/2,tr[rt].rs=tr[rt<<1|1].rs;
tr[rt].rsum=tr[rt<<1|1].rsum,tr[rt].ls=tr[rt<<1|1].ls;
}
if(tr[rt<<1|1].fla){
tr[rt].rsum=(tr[rt<<1|1].r-tr[rt<<1].ls+2)/2,tr[rt].ls=tr[rt<<1].ls;
tr[rt].lsum=tr[rt<<1].lsum,tr[rt].rs=tr[rt<<1].rs;
}
}
}else tr[rt].fla=0,tr[rt].sum=tr[rt<<1].sum+tr[rt<<1|1].sum;
}else{
tr[rt].sum=tr[rt].lsum=tr[rt].sum=tr[rt].fla=tr[rt].l=tr[rt].r=tr[rt].ls=tr[rt].rs=0;
if(tr[rt<<1].sum){
tr[rt].sum=tr[rt<<1].sum,tr[rt].lsum=tr[rt<<1].lsum,tr[rt].rsum=tr[rt<<1].rsum,tr[rt].fla=tr[rt<<1].fla;
tr[rt].l=tr[rt<<1].l,tr[rt].r=tr[rt<<1].r,tr[rt].ls=tr[rt<<1].ls,tr[rt].rs=tr[rt<<1].rs;
}
if(tr[rt<<1|1].sum){
tr[rt].sum=tr[rt<<1|1].sum,tr[rt].lsum=tr[rt<<1|1].lsum,tr[rt].rsum=tr[rt<<1|1].rsum,tr[rt].fla=tr[rt<<1|1].fla;
tr[rt].l=tr[rt<<1|1].l,tr[rt].r=tr[rt<<1|1].r,tr[rt].ls=tr[rt<<1|1].ls,tr[rt].rs=tr[rt<<1|1].rs;
}
}
}
void add(ll rt,ll l,ll r,ll x,ll d){
if(l==r){
tr[rt].fla=d;
if(d)tr[rt].l=tr[rt].r=tr[rt].ls=tr[rt].rs=x,tr[rt].sum=tr[rt].lsum=tr[rt].rsum=1;
else tr[rt].l=tr[rt].r=tr[rt].ls=tr[rt].rs=0,tr[rt].sum=tr[rt].lsum=tr[rt].rsum=0;
return;
}
ll mid=(r+l)>>1;
if(x<=mid)add(rt<<1,l,mid,x,d);
else add(rt<<1|1,mid+1,r,x,d);
pushup(rt);
}
int main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>a[i].x,a[i].k=i;
sort(a+1,a+n+1,cmp);
for(int i=1;i<=m;i++)add(1,1,n,a[i].k,1);
for(int i=1,p=m;i<=n-m+1;i++){ //固定最小值
while(tr[1].sum<m&&p<n)add(1,1,n,a[++p].k,1); //不断增大最大值
if(tr[1].sum>=m)ans=min(ans,a[p].x-a[i].x); //tr[1].sum包含了整个区间的最优选择，直接判断其是否能取到 m 个
add(1,1,n,a[i].k,0); //把没用的的数字去除，维护线段树的正确性
}
cout<<ans;
}