题目要求：给一段序列a，求满足每个元素在原序列里位置至少相隔k的最长上升子序列。
这个问题我们有3种解决方法，LIS魔改算法，线段树，动态规划。在这篇博客中，我们讨论的是通过线段树来解决这个问题。
我们将我们构造的树的叶子节点用来储存1到这一点的满足题目要求的最长上升子序列的长度，然后不断维护最大值。
具体代码如下：
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn=1e5+9;
int T[maxn<<2],a[maxn],len[maxn];//len[i]表示1-i这段序列满足条件的最长上升子序列的长度
void pushup(int rt){
T[rt]=max(T[rt<<1],T[rt<<1|1]);
}
void update(int l,int r,int pos,int val,int rt){
if(l==r){
T[rt]=val;
return;
}
int m=(l+r)>>1;
if(m>=pos)update(l,m,pos,val,rt<<1);
else update(m+1,r,pos,val,rt<<1|1);
pushup(rt);
}
int query(int l,int r,int ql,int qr,int rt){
if(l>=ql&&r<=qr)return T[rt];
int m=(l+r)>>1;
int ans=0;
if(m>=ql)ans=query(l,m,ql,qr,rt<<1);
if(m<qr)ans=max(ans,query(m+1,r,ql,qr,rt<<1|1));
return ans;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
int i,j,k,n;
while(cin>>n>>k){
memset(T,0,sizeof(T));
memset(len,0,sizeof(len));
int mx=-1;
for(i=1;i<=n;i++){
cin>>a[i];if(a[i]>mx)mx=a[i];
}mx++;
int ans=0;
for(i=1;i<=n;i++){
if(i-k-1>0)update(1,mx,a[i-k-1]+1,len[i-k-1],1);
if(a[i]!=0)len[i]=query(1,mx,1,a[i],1)+1;//a[i]==0时查找会出现错误
else len[i]=1;
if(len[i]>ans)ans=len[i];
}
cout<<ans<<endl;
}
}
这一段代码最难理解的可能就是第二个for循环里的操作了，有同学不理解更新为什么要将a[i-k-1]+1作为更新的位置（+1是因为题目要求严格上升），别急，我们先往后面看，发现查询操作时也是类似的查询1-a[i]这段区间，说到这里可能有些人已经懂了，为什么要将a数组作为更新操作查询操作的位置信息呢？因为我们找出来的序列得是上升的。如果还是不懂的话我也没办法，自己好好思考吧。