思路：利用线段树求出 a[i] （以 下表i所在数为结尾的最长不下降序列）， 然后刷新线段树，从大到小 重新放入线段树 ，求出 区间 （i+k+1~n）之间 最大的不下降子序列。 代码
点击查看代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e7+9;
int e[N],a[N],lazy[N];
int b[N],c[N];
int aa[N],bb[N];
void buidtree(int k,int l,int r)
{
if(l==r)
{
e[k]=0;
return ;
}
int mid=(l+r)>>1;
buidtree(k<<1,l,mid);
buidtree(k<<1|1,mid+1,r);
e[k]=max(e[k<<1],e[k<<1|1]);
return ;
}
void push(int k,int l,int r,int w,int y)
{
if(l==r)
{
e[k]=y;
return ;
}
int mid=(l+r)>>1;
if(mid<w)
{
push(k<<1|1,mid+1,r,w,y);
}
else push(k<<1,l,mid,w,y);
e[k]=max(e[k<<1],e[k<<1|1]);
return ;
}
int cha(int k,int l,int r,int x,int y)
{
if(x<=l&&y>=r)
{
return e[k];
}
int mid=(l+r)>>1;
int ans=0;
if(mid>=x)
{
ans=max(ans,cha(k<<1,l,mid,x,y));
}
if(y>mid)
{
ans=max(ans,cha(k<<1|1,mid+1,r,x,y));
}
return ans;
}
struct node
{
int x,y;
}p[N];
bool cam(node x,node y)
{
if(x.x!=y.x)
return x.x<y.x;
return x.y<y.y;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int n,d,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>d;
c[i]=d;
p[i].x=d;
p[i].y=i;
}
buidtree(1,1,n);
sort(p+1,p+1+n,cam);
for(int i=1;i<=n;i++)
{
int x=p[i].y;
int y=p[i].x;
y=cha(1,1,n,1,x)+1;
a[x]=y;
push(1,1,n,x,y);
}
int ans=0,j=n;
buidtree(1,1,n);
for(int i=0;i<=n*5;i++)
{
e[i]=0;
}
for(int i=n;i>=1;--i)
{
int x=p[i].y;
int y=p[i].x;
int s=x+m+1;
if(s>n)
{
ans=max(ans,a[x]+n-x);
}
else
{
ans=max(ans,a[x]+m+cha(1,1,n,s,n));
}
y=cha(1,1,n,x,n)+1;
push(1,1,n,x,y);
// b[x]=y;
j--;
}
cout<<ans;
return 0;
}