hdu 3450

吐吐槽吧：本来思路完全对了，但是那个二分查找搞错了，我还以为一个就可以了，结果查找上界和下界分别要一个查找函数（WA时就看了一下别人的代码，发现别人都是用两个查找函数的，模仿别人写的查找函数），自己得好好揣摩揣摩。。。

还有就是最后的结果可能是负数。。。因为get_sum的值是小于9901的，而N的值可大于9901

#include <cstdio>
#include <cstring>
#include <algorithm>

const int mod = 9901;
const int maxn = 100000 + 100;

int a[maxn];
int val[maxn];
int c[maxn];
int N,D,num;

int binary_find1(int x,int l,int r)
{
    int ans = r;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(val[mid] <= x) l = mid + 1,ans = mid;
        else r = mid - 1;
    }

    return ans;
}

int binary_find2(int x,int l,int r)
{
    int ans = l;
    while(l <= r)
    {
        int mid = (l + r) / 2;
        if(val[mid] < x) l = mid + 1;
        else r = mid - 1,ans = mid;
    }
    return ans;
}
int get_sum(int x)
{
    int sum = 0;
    while(x > 0)
    {
        sum += c[x];
        sum = sum % mod;
        x -= (x & (-x));
    }

    return sum;
}

void insert(int x,int v)
{
    while(x < num)
    {
        c[x] += v;
        c[x] = c[x] % mod;
        x += (x & (-x));
    }
}

int main()
{
    while(scanf("%d%d",&N,&D) == 2)
    {
        for(int i = 1;i <= N;i ++)
        {
            scanf("%d",&a[i]);
            val[i] = a[i];
        }
        std::sort(val + 1,val + N + 1);
        num = 2;
        for(int i = 2;i <= N; i ++)
        {
            if(val[i] != val[i -1])
                val[num ++] = val[i];
        }
        memset(c,0,sizeof(c));
        for(int i = 1;i <= N;i ++)
        {
            int k = binary_find1(a[i],1,num - 1);
            int x = binary_find1(a[i]+ D,1,num -1);
            int y = binary_find2(a[i] - D,1,num-1); 
            int ans = 1;
            ans += get_sum(x);
            ans -= get_sum(y - 1);
            ans %= mod;
            insert(k,ans);
        }

        printf("%d\n",((get_sum(num-1) - N)%mod +mod)%mod);
    }

    return 0;
}