题意很简单，让求序列中两个数id相差大于d的数字组成的最长上升子序列。
这题目最关键的一点就是如何废除跟当前数字id相差小于等于d的数字的作用，这里使用了变形的延迟更新求解。
题目有两种解法，线段树或者直接dp。
线段树：
这个想到不难，看到那么大的数据量，很自然想到这点。线段树求最长上升子序列倒是挺容易的，难点在于不能排除跟当前节点id相差小于d+1的值的影响。这里采用一个数组len【i】记录第i个数的满足题意的小明序列长度，然后，关键来了，如果想要消除影响，一个可行的方案就是当做这个数没出现过，也就是直接延迟更新线段树，对小于d+1的数，先不更新，等用得到的时候再更新，此时len【i】记录的刚好是该数字更新时的值，直接用该数字的值当做在线段树中的位置，然后便可以很方便的求解了。
变形LIS：
LIS的nlogn算法不难，解这个题的关键也是延迟更新，即使得与当前位置相差小于d+1的数暂时不去更新记录每个长度最小尾部的数组，等到需要时再给与更新即可。关键在于，更新时普通的nlogn对每个数都是确定可以更新的，但是对当前问题则不一定，假设d=2，序列为1,2,3,4,5，那么每个值的小明序列值应该为1,1,1,2,2，前三个都形成对第一个数的更新，此时显然要取能更新到的值的最小值，也就是说后面的数不一定更新前面的数，如第五个数是会用第二个数更新，但是第二个数是对dp[1]的更新，此时不能更新，因为第二个数不是比当前dp[1]（第一个数将dp[1]更新成1）更优的解，这点解决了，这题也就没什么问题了。
总结：
这道题目无论哪种写法，关键都在于延迟更新，即对那些暂时不能用到的值不予以更新，而是记录他们的状态，等用得到的时候再更新，这个思路很重要，用不到就先不管你，等用到时再拉你出来，很简单实用的解题思想。
代码：
线段树：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define delf int m=(l+r)>>1
const int MAX=111111;
int sum[444444];
int m[MAX];
int dp[MAX];
int max(int a,int b)
{
return a>b?a:b;
}
void pushup(int rt)
{
sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}
void update(int k,int b,int l,int r,int rt)
{
if (l==r)
{
sum[rt]=b;
return ;
}
delf;
if (m>=k)
update(k,b,lson);
else
update(k,b,rson);
pushup(rt);
return ;
}
int query(int L,int R,int l,int r,int rt)
{
if (R<L)
return 0;
if (L<=l&&r<=R)
return sum[rt];
delf;
int s=0;
if (m>=L)
s=max(s,query(L,R,lson));
if (m<R)
s=max(s,query(L,R,rson));
return s;
}
int main()
{
int n,d;
while (~scanf("%d%d",&n,&d))
{
memset(sum,0,sizeof(sum));
memset(m,0,sizeof(m));
memset(dp,0,sizeof(dp));
int ans=0;
for (int i=1;i<=n;i++)
{
scanf("%d",&m[i]);
if (i-d-1>0)
update(m[i-d-1],dp[i-d-1],0,100010,1); //延迟更新，使得与当前节点距离小于等于d的节点不起作用（未更新线段树）
dp[i]=query(0,m[i]-1,0,100010,1)+1;
ans=max(dp[i],ans);
}
printf("%d\n",ans);
}
}
变形LIS：
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int dp[100010]; //记录每个长度的小明序列长度的最小值
int len[100010]; //记录以当前节点结尾的最长小明序列长度
int ll[100010]; //记录到该节点的最长小明序列长度
int m[100010];
int find(int v,int l)
{
int low=1,high=l;
//cout<<low<<" "<<high<<endl;
while (low<=high)
{
//cout<<low<<" "<<high<<endl;
int mid=(low+high)>>1;
if (dp[mid]>=v)
high=mid-1;
else
low=mid+1;
}
return low;
}
int main()
{
int n,d;
while (~scanf("%d%d",&n,&d))
{
memset(dp,-1,sizeof(dp));
int ans=0;
for (int i=1;i<=n;i++)
{
scanf("%d",&m[i]);
len[i]=find(m[i],i-d-1>0?ll[i-d-1]:0);
if (i-d>0) //延迟更新小明序列的长度的末尾值，使得与当前节点相差小于等于d的节点不起作用
{
int t=len[i-d];
/*
例如d=2时，下标为1，2，3的点都会试图更新dp[1]，此时取三者
能取到（与当前计算节点距离大于d）的最小值
*/
if (dp[t]==-1||dp[t]>m[i-d])
dp[len[i-d]]=m[i-d];
}
ans=ans>len[i]?ans:len[i]; //取最大值
ll[i]=ans;
//cout<<len[i]<<endl;
}
cout<<ans<<endl;
}
}