ZOJ 3349 Special Subsequence

5 2
1 4 3 6 5

5 0
1 2 3 4 5

3
1

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

const int maxn=101000;

int n,d,a[maxn],b[maxn],t,dp[maxn];

#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

int tree[maxn<<2];

void push_up(int l,int r,int rt)
{
    tree[rt]=max(tree[rt<<1],tree[rt<<1|1]);
}

void build(int l,int r,int rt)
{
    if(l==r)
    {
        tree[rt]=0;
        return ;
    }
    int m=(l+r)>>1;
    build(lson); build(rson);
    push_up(l,r,rt);
}

int query(int l,int r,int rt,int L,int R)
{
    if(L<=l&&r<=R)
    {
        return tree[rt];
    }
    int m=(l+r)>>1;
    int ret=-1;
    if(L<=m) ret=max(ret,query(lson,L,R));
    if(R>m) ret=max(ret,query(rson,L,R));
    return ret;
}

void update(int l,int r,int rt,int P,int V)
{
    if(l==r)
    {
        tree[rt]=V;
        return ;
    }

    int m=(l+r)>>1;

    if(P<=m) update(lson,P,V);
    else update(rson,P,V);

    push_up(l,r,rt);
}

int main()
{
while(scanf("%d%d",&n,&d)!=EOF)
{
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        b[i]=a[i];
    }
    sort(b+1,b+n+1);
    int t=unique(b+1,b+n+1)-b-1;
    memset(dp,0,sizeof(dp));
    dp[1]=1;
    build(1,n,1);

    for(int i=1;i<=n;i++)
    {
        int rt=lower_bound(b+1,b+t+1,a[i])-b;
        int l=lower_bound(b+1,b+t+1,a[i]-d)-b;
        int r=upper_bound(b+1,b+t+1,a[i]+d)-(b+1);
        dp[i]=query(1,n,1,l,r)+1;
        update(1,n,1,rt,dp[i]);
    }

    int ans=-1;
    for(int i=1;i<=n;i++)
        ans=max(ans,dp[i]);

    printf("%d
",ans);
}
    return 0;
}