hdu 3450 樹狀數組優化dp

hdu 3450 樹狀數組優化dp

題意就不說了； hdu2227差不多只不過這道題不是遞增 而是相鄰差不超過d 其實是為都一樣， 也有差別；

這道題沒說范圍 並且樹之間的大小關系對結果有影響，所以樹狀數組裡根據原來id來求，由於數值很大 所以還是用到離散化 這裡的離散化感覺和映射差不多，離散化用來查找id；

當num【i】的id是x是，dp【i】表示方案數 很明顯dp【i】=sun（dp【j】，j

#include
#include
#include
#include
using namespace std;

#define mod 9901

int num1[100010],num2[100010],mark[100010],tt,n;
int coun[100010];
int update(int a,int b)
{
    for(int i=a;i<=n;i+=(i&-i))
    {
        coun[i]+=b;
        coun[i]%=mod;
    }
    return 0;
}
int find(int a)
{
    int s=0;
    for(int i=a;i>=1;i-=(i&-i))
    {
        s+=coun[i];
        s%=mod;
    }
    return s;
}
int searchr(int a)
{
    int left=1,right=tt,now;
    while(left<=right)
    {
        int mid=(left+right)/2;
        if(mark[mid]<=a)    
        {   
            now=mid;
            left=mid+1;
        }
        else 
        {
            right=mid-1;
        }
    }    
    return now;
}
int searchl(int a)
{
    int left=1,right=tt;
    while(left<right)
    { 
        int mid=(left+right)/2;
        if(mark[mid]<a) left=mid+1;
        else if(mark[mid]==a) return mid;
        else right=mid;
    }
    return left;
}
int main()
{
    int i,j,d;
    while(~scanf("%d%d",&n,&d))
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&num1[i]);
            num2[i]=num1[i];
        }
        sort(num2+1,num2+1+n);
        tt=0;         
        num2[0]=-1;
        for(i=1;i<=n;i++)
        {
            if(num2[i]!=num2[i-1])
            {
                tt++;
                mark[tt]=num2[i];
            }
        }
        memset(coun,0,sizeof(coun));
        int sum=0;
        int x=searchl(num1[1]);
        for(i=1;i<=n;i++)
        {
            int left=searchl(num1[i]-d)-1;
            int right=searchr(num1[i]+d);
            int now=searchl(num1[i]);
            int s=find(right)-find(left);
            s=(s%mod+mod)%mod;
            sum+=s;
            sum%=mod;
            update(now,s+1);
        }
        printf("%d\n",sum);
    }
    return 0;
}