学步园

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=100009;
struct Sort_a
{
    int a,i;
    Sort_a(int x=0,int y=0){a=x;i=y;}
    bool operator<(const Sort_a &tt) const {return a<tt.a;}
}pa[N];
int dp[N],a[N],pos[N],tree[N<<2];

void build(int l,int r,int id)
{
    tree[id]=0;
    if(l<r)
    {
        int mid=(l+r)>>1;
        build(l,mid,id<<1);
        build(mid+1,r,id<<1|1);
    }
}

void pushup(int id)
{
    tree[id]=max(tree[id<<1],tree[id<<1|1]);
}

void updata(int k,int l,int r,int id)
{
    if(l==k && k==r)
    {
        tree[id]=dp[pa[k].i];
        return;
    }
    int mid=(l+r)>>1;
    if(k<=mid) updata(k,l,mid,id<<1);
    if(k>mid) updata(k,mid+1,r,id<<1|1);
    pushup(id);
}

int find(int L,int R,int l,int r,int id)
{
    if(L<=l && r<=R) return tree[id];
    int mid=(l+r)>>1,ans1=0,ans2=0;
    if(L<=mid) ans1=find(L,R,l,mid,id<<1);
    if(R>mid) ans2=find(L,R,mid+1,r,id<<1|1);
    return max(ans1,ans2);
}

int main()
{
    int n,d;
    while(scanf("%d %d",&n,&d)==2)
    {
        int i,j,k;
        for(i=0;i<n;i++)
        {
            scanf("%d",&a[i]);
            pa[i].a=a[i];
            pa[i].i=i;
        }
        sort(pa,pa+n);
        for(i=0;i<n;i++)
        {
            pos[pa[i].i]=i;
            dp[i]=0;
        }
        build(0,n-1,1);
        for(i=0;i<n;i++)
        {
            int l,r;
            l=lower_bound(pa,pa+n,Sort_a(a[i]-d))-pa;
            r=upper_bound(pa,pa+n,Sort_a(a[i]+d))-pa-1;
            dp[i]=find(l,r,0,n-1,1)+1;
            updata(pos[i],0,n-1,1);
        }
        int ans=0;
        for(i=0;i<n;i++) ans=max(ans,dp[i]);
        printf("%d\n",ans);
    }
    return 0;
}