学步园

这个题的灵感来自与前几天做的一个题，思路想好之后，忽然发现自己好想会做这类题目了，不过还是要折腾老久，因为好多细节处理不好。

wa了好多好多次了，终于加了个mod就过了，尼玛。。。。。。

[code lang="cpp"]
i64 query(int pos)
{
    i64 sum = 0 ;
    while(pos > 0 )
    {
        sum += f[pos] %mod;
        pos -= lowbit(pos);
    }
    return sum;
}
void update(int pos,i64 val)
{
    while(pos <= nn)
    {
        f[pos] += val % mod;
        pos += lowbit(pos);
    }
}
int main()
{
    while(scanf("%d%d",&n,&d)!=EOF)
    {
        nn1 = 0 ;
        for(int i = 0 ; i < n ; i++)
        {
            RD(a[i]);
            d1[nn1 ++ ] = a[i];
            d1[nn1 ++ ] = a[i] - d - 1;
            d1[nn1 ++ ] = a[i] + d;
        }
        sort(d1,d1+nn1);
        nn = 0;
        for(int i=1; i<nn1; i++)
            if(d1[i] != d1[nn])
                d1[++nn] = d1[i];
        for(int i=0; i<n; i++)
        {
            pos[i] = lower_bound(d1,d1+nn,a[i]) - d1 + 1;
        }
        clr(f,0);
        clr(dp,0);
        for(int i=0; i<n; i++)
        {
            int pos1,pos2;
            i64 tmp1,tmp2,tmp;
            pos1 = lower_bound(d1,d1+nn,a[i] + d ) - d1 + 1;
            pos2 = lower_bound(d1,d1+nn,a[i] - d - 1  ) - d1 + 1;
            tmp = query(pos1) - query(pos2) + mod + mod ;
            dp[pos[i]] += tmp % mod;
            update(pos[i],(tmp + 1) % mod );
        }
        i64 ans ;
        ans = 0;
        for(int i=1 ; i<=nn; i++) ans += dp[i] % mod;
        PR(ans%mod);
    }
    return 0;
}
[/code]