hdu3450 Counting Sequences(dp+ 이산화 + 트리 배열 최적화)

Problem Description For a set of sequences of integers｛a1,a2,a3,…an｝, we define a sequence｛ai1,ai2,ai3…aik｝in which 1<= i1 < i2< i3= 2, and the neighboring 2 elements have the difference not larger than d, it will be defined as a Perfect Sub-sequence. Now given an integer sequence, calculate the number of its perfect sub-sequence.
Input Multiple test cases The first line will contain 2 integers n, d(2<=n<=100000,1<=d=<=10000000) The second line n integers, representing the suquence
Output The number of Perfect Sub-sequences mod 9901
Sample Input 4 2 1 3 7 5
Sample Output 4
대체적인 의미: n개의 수를 주고 길이가 2보다 크고 인접한 두 개의 차액이 d보다 크지 않은 서열의 개수를 찾아라.
사고방식:hdu2227과 그 문제는 차이가 많지 않고 먼저 이산화된 다음에 나무 모양의 수조로 dp를 최적화시킨다. 마지막으로 모형을 뽑을 때 주의해야 한다.
코드는 다음과 같다.

#include 
#include 
#include   
#include   
#define ll long long int   
using namespace std;
const int N=1e5+5; 
const int mod=9901;
int dp[N];
int n,d;
int a[N],b[N],HASH[N];
int tot;
int lowbit(int x)
{
    return x&-x;
}

int sum(int x)
{
    int s=0;
    while(x>0)
    {
        s=(s+dp[x])%mod;
        x=x-lowbit(x);
    }
    return s;
}

void add(int x,int date)
{
    while(x<=n)
    {
        dp[x]=(dp[x]+date)%mod;
        x=x+lowbit(x);
    }
}

int findR(int v)
{
    int i=1,j=tot+1,mid;

    while(i2;
        if(HASH[mid]<=v)    
            i=mid+1;
        else 
            j=mid;
    }
    return i-1;
}

int findL(int v)
{
    int i=1,j=tot+1,mid;

    while(i2;
        if(HASH[mid]1;
        else 
            j=mid;
    }
    return i-1;
}

int main()  
{
    while(~scanf("%d%d",&n,&d))
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        tot=1;
        HASH[1]=b[1];
        for(int i=2;i<=n;i++)
            if( b[i]!=b[i-1] )
                HASH[++tot]=b[i];

        for(int i=1;i<=n;i++)
        {
            int L=findL(a[i]-d),id=findL(a[i])+1,R=findR(a[i]+d);
            int tmp=sum(R)-sum(L);
            add(id,tmp+1);
        }
        printf("%d
",((sum(tot)-n)%mod+mod)%mod);
    }   
    return 0;  
}