题意：

①首先定义S为一个有序序列，S={ A1 , A2 , A3 , ... , An }，n为元素个数 ；

　　②然后定义Sub为S中取出的一个子序列，Sub={ Ai1 , Ai2 , Ai3 , ... , Aim }，m为元素个数 ；

　　③其中Sub满足 Ai1 < Ai2 < Ai3 < ... < Aij-1 < Aij < Aij+1 < ... < Aim ；

　　④同时Sub满足对于任意相连的两个Aij-1与Aij都有 ij - ij-1 > d (1 < j <= m， d为给定的整数)；

　　⑤显然满足这样的Sub子序列会有许许多多，而在取出的这些子序列Sub中，元素个数最多的称为“小明序列”(即m最大的一个Sub子序列)。

　　例如：序列S={2,1,3,4} ，其中d=1；

　　可得“小明序列”的m=2。即Sub={2,3}或者{2,4}或者{1,4}都是“小明序列”。

　　当小明发明了“小明序列”那一刻,情绪非常激动，以至于头脑凌乱，于是他想请你来帮他算算在给定的S序列以及整数d的情况下，“小明序列”中的元素需要多少个呢？

 

思路：

DP的思想，但是只能想到N^2的算法。嘿嘿正好题目有说(0<=Ai<=10^5)，那就是了，用线段树保存最值。

每次做题都要考虑周全，边界什么的，，

d=0时单独用贪心的方法算，其实不用也可以，。

 

代码：

int const N = 100005;int a[N], f[N];int F[N<<2];int n,d;void PushUp(int rt){    F[rt]=max( F[rt<<1],F[rt<<1|1] );    return;}void build(int l,int r,int rt){    if(l==r){        F[rt]=0;        return;    }    int m=(l+r)>>1;    build(lson);    build(rson);    PushUp(rt);}void update(int pos,int x,int l,int r,int rt){    if(l==r){        F[rt]=max( F[rt],x );        return;    }    int m=(l+r)>>1;    if(pos<=m)        update(pos,x,lson);    else        update(pos,x,rson);    PushUp(rt);}int query(int L,int R,int l,int r,int rt){    if(L<=l && r<=R){        return F[rt];    }    int m=(l+r)>>1;    int res=0;    if(L<=m)        res=max( res,query(L,R,lson) );    if(m
     
      d[cn]){            d[++cn]=a[i];        }else{            int pos=lower_bound(d+1,d+1+cn,a[i])-d;            d[pos]=a[i];        }    }    return cn;}int main(){    while(scanf("%d%d",&n,&d)!=EOF){        int es=-inf;        rep(i,1,n){            scanf("%d",&a[i]);            es=max( es,a[i] );        }        if(d==0){            int ans=proc1();            printf("%d\n",ans);        }else{            build(0,es,1);            int ans=1;            rep(i,1,n){                if(i-d-1<=0){                    f[i]=1;                }else{                    update(a[i-d-1],f[i-d-1],0,es,1); //pos,x,l,r,rt                    if(a[i]==0){                        f[i]=1;                        continue;                    }                    int t=query(0,a[i]-1,0,es,1); //L,R,l,r,rt                    f[i]=t+1;                    ans=max( ans,f[i] );                }            }            printf("%d\n",ans);        }    }    return 0;}