luogu P9474 [yLOI2022] 长安幻世绘 详细题解
看到很多大佬的题解直接讲了做法，本蒟蒻看得不是很懂，调了很久才把这题做出来，于是写了这篇比较详细的题解谈一下我做这题从头到尾的思路，希望对各位有帮助 qwq。
思路
我们首先思考这样一个问题，如果已经知道最终答案对应的最大值和最小值，又不知道题目给的 \(m\)，该如何去求这样选出的子列的长度呢？
显然，我们要让原序列中大小在最大值和最小值之间的所有数都尽可能多地选进子列（因为如果有可以选的但没有选完，就可以把选的子列中最小值或最大值替换中间那些没选的，这样会得到一种极差更小的情况，与条件矛盾），但是这些数在原序列中可能是连续的，不能都选进去，于是分别考虑这些可以选的数在原序列中构成的每一个最长连续段，容易发现，只有隔一个选一个才能选的尽可能多，如果段长是偶数，最多选一半，段长是奇数，首尾都选了，最多选段长加 \(1\) 的一半。实际上，最多选的数的个数就是段长除以 \(2\) 并向上取整，而不同段选的数互不干扰，所以当前子列的长度就是每段可选的最多个数加起来。
这样就很容易想到一种暴力枚举的方法，我们只需要枚举所有的最大值和最小值，其中必然有一个组合对应着最终答案，每次 \(O(n)\) 算出选出的子列长度，在所有长度为 \(m\) 的子列中找极差最小的即可，时间复杂度为 \(O(n^3)\)。
考虑在暴力枚举的基础上进行优化，可以发现，有大量的情况找到的子列长度都不为 \(m\)，不会影响答案，浪费了很多时间，如何尽量让枚举的情况长度都是 \(m\) 呢？由于我们枚举的是最大值和最小值，是有大小关系的，尝试把原数列从小到大排序，形成一个有单调性的序列，这样就可以使用双指针去枚举最大值和最小值了，用左指针枚举最小值，右指针枚举最大值，可以发现左指针向右移动的时候右指针一定不可能向左移动（因为左指针让子列长度变小或不变，为了让找到的子列长度更接近 \(m\)，右指针只能向右移或不动，向左移就会得到一个更小的子列长度，对答案一定是没有意义的），满足双指针法两个指针都单调不减的性质，这样右指针和左指针移动次数都最多只有 \(n\) 次，减少了暴力方法中大量没有意义的枚举次数。
但是 \(O(n^2)\) 的复杂度仍然不能通过此题，我们便着眼于子段长度的求法上，朴素方法需要每次遍历整个原序列来找到每一个最长连续段的长度，但我们发现在双指针的枚举过程中，当前枚举的子列每次只会有一个数发生变化，左指针移动则代表原数列在当前区间内可以选的数会少一个，右指针移动则会增加一个，而其他的数都是不变且有序的。所以便想到用一种数据结构去维护当前在原数列中可以选的数（不是当前子列），这里以线段树为例，每次增加一个数和减少一个数都是标准的单点修改，而要得到每次选出的子列长度则稍微有些难度，我们可以只考虑每次单点修改后子列长度的变化：如果新增了一个可以选的数，那么子列长度的变化只与这个数在原数列中左右相邻的最长连续段有关，分以下 \(3\) 种情况讨论：
-
如果左右都没有相邻的最长连续段（即左右两数都不在当前可以选的数范围内），则原序列中会多一个长度为 \(1\) 的最长连续段，选的子列长度会多 \(1\)。
-
如果仅有一侧有相邻的最长连续段，则只会受这个相邻的最长连续段影响，显然，如果其长度为偶数，可以在以前的基础上多选一个，子列长度多 \(1\)，奇数则不行，子列长度不受影响。
-
如果两侧都有相邻的最长连续段，则只有在两侧最长连续段长度都为偶数的时候可以多选这个数，否则子列长度不受影响。
而对于删除（即减少了一个可以选的数）的情况，实际上和新增是一样的，删除相当于是去除原来新增这个数对子列长度的影响，与上面的判断方法相同，在新增是需要增加子列长度时，减少子列长度即可（即与新增的操作相反）。
而如何找到左右相邻的最长连续段呢？使用线段树维护每个区间内可选数的最长前缀和最长后缀，由线段树的区间可合并性质，递归将数列第一个数到当前数的左边一个数的区间合并，新区间的最长后缀就是左边相邻的最长连续段，而递归将当前数的右边一个数到数列最后一个数的区间合并，新区间的最长前缀就是右边相邻的最长连续段（具体实现见代码，如果还是不太理解区间前缀和后缀的维护，可以先去看看这题）。
线段树每次单点修改和区间合并的复杂度都是 \(O(\log n)\)，总复杂度为 \(O(n \log n)\)，可以通过此题。
Code
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=100010;
struct Node
{
int pre,suf;//当前区间的最长前缀和最长后缀
int pl,pr;//区间的左右端点
}tree[N<<2];
Node pushup(Node &p,Node a,Node b)//pushup直接合并两个区间，便于找最长前缀和最长后缀
{
p.pl=a.pl,p.pr=b.pr;
if(a.pre==a.pr-a.pl+1) p.pre=a.pre+b.pre;//如果左区间的前缀占满了整个左区间，则合并时也要把右区间算进去
else p.pre=a.pre;
if(b.suf==b.pr-b.pl+1) p.suf=b.suf+a.suf;//如果右区间的前缀占满了整个左区间，则合并时也要把左区间算进去
else p.suf=b.suf;
return p;
}
void build(int p,int pl,int pr)//因为最开始维护的区间是空的，所以也可以不用建树，这里只是方便记录每个区间的左右端点
{
tree[p].pl=pl,tree[p].pr=pr;
if(pl==pr) return;
int mid=(pl+pr)>>1;
build(p<<1,pl,mid);
build(p<<1|1,mid+1,pr);
}
void update(int p,int id,int data)//标准的单点修改
{
if(tree[p].pl==tree[p].pr)
{
tree[p].pre=tree[p].suf=data;
return;
}
int mid=(tree[p].pl+tree[p].pr)>>1;
if(mid>=id) update(p<<1,id,data);
if(mid<id) update(p<<1|1,id,data);
pushup(tree[p],tree[p<<1],tree[p<<1|1]);
}
Node mergeL(int p,int id)//合并最左端到编号为id的位置的区间
{
if(tree[p].pr<=id) return tree[p];
int mid=(tree[p].pl+tree[p].pr)>>1;
Node t;
//如果当前区间中点在id右侧，就不用管右子区间，递归找左子区间
if(mid>=id) return mergeL(p<<1,id);//注意理解哪里该取等，这里容易写错
//如果当前区间中点在id左侧，那整个左区间一定在需合并的左区间中，右区间则继续递归找在1~id范围内的区间
if(mid<id) return pushup(t,tree[p<<1],mergeL(p<<1|1,id));
}
Node mergeR(int p,int id)//合并编号为id的位置到最右端的区间
{
if(tree[p].pl>=id) return tree[p];
int mid=(tree[p].pl+tree[p].pr)>>1;
Node t;
if(mid<id) return mergeR(p<<1|1,id);
if(mid>=id) return pushup(t,mergeR(p<<1,id),tree[p<<1|1]);
}
int n,m,ans=0x3f3f3f3f;
pair<int,int> lamp[N];//pair中first存数值大小（灯的高度），second存其在原数列中的编号，便于直接sort排序
int main()
{
scanf("%d%d",&n,&m);
build(1,1,n);
for(int i=1;i<=n;i++) scanf("%d",&lamp[i].first),lamp[i].second=i;
sort(lamp+1,lamp+1+n);//对原数列从小到大排序
int l,r=0,cnt=0;//通过左右指针l和r枚举区间，cnt表示当前情况下的子列长度
for(l=1;l<=n;l++)
{
int Lsuf,Rpre;//左边最长后缀和右边最长前缀
while(cnt<m&&r<n)//一直右移右指针直到子列长度达到m
{
r++;
//维护的区间中新增一个可以选的数（当前右指针处）
update(1,lamp[r].second,1);
if(lamp[r].second==1) Lsuf=0;
else Lsuf=mergeL(1,lamp[r].second-1).suf;
if(lamp[r].second==n) Rpre=0;
else Rpre=mergeR(1,lamp[r].second+1).pre;
//会增加子列长度的三种情况
if((!Lsuf&&!Rpre)||(!Rpre&&Lsuf&&Lsuf%2==0)||(!Lsuf&&Rpre&&Rpre%2==0)||(Lsuf&&Rpre&&Lsuf%2==0&&Rpre%2==0)) cnt++;
}
if(cnt==m)
{
//左指针右移，维护的区间中删除一个可以选的数（当前左指针处）
update(1,lamp[l].second,0);
if(lamp[l].second==1) Lsuf=0;
else Lsuf=mergeL(1,lamp[l].second-1).suf;
if(lamp[l].second==n) Rpre=0;
else Rpre=mergeR(1,lamp[l].second+1).pre;
//会减少子列长度的三种情况
if((!Lsuf&&!Rpre)||(!Rpre&&Lsuf&&Lsuf%2==0)||(!Lsuf&&Rpre&&Rpre%2==0)||(Lsuf&&Rpre&&Lsuf%2==0&&Rpre%2==0)) cnt--;
ans=min(lamp[r].first-lamp[l].first,ans);//每枚举到一种符合要求情况就更新一次最小答案
}
}
printf("%d",ans);
return 0;
}
感谢各位dalao的阅读 qwq。