hdu3450

分析：首先要知道有递推公式dp[i] = Sigma(dp[j])，dp[i]表示第i个数结尾的完美子序列的个数，|a[i] - a[j]| <= d，j<i。直接这样做的时间复杂度为n^2，对于最大有100000的n还是会超时的，留意到公式是连续加的（j<i 时，以[a[i] - d, a[i] + d]区间里面的数结尾的完美子序列个数相加），其实j>i的[a[i] - d, a[i] + d]区间里面的数结尾的完美子序列个数也可以加进去，只要初始化都为0，正因为这样可以用树状数组对这种加法进行加速，只要先用二分查找出区间两端点对应在树状数组里面的下标。

 #pragma warning(disable:4996)

 #include <cstdio>

 #include <set>

 #include <stack>

 #include <vector>

 #include <algorithm>

 #include <map>

 #define MOD 9901

 using namespace std;

 int bit[];//bit -- binary indexed tree

 int a[], order[], len;

 int lowBit(int x){

     return x & (-x);

 }

 //size是数组的大小，val是增量

 void update(int idx, int size, int val){

     while (idx <= size){

         bit[idx] += val;

         if (bit[idx] >= MOD){

             bit[idx] %= MOD;

         }

         idx += lowBit(idx);

     }

 }

 //求a[1]到a[idx]的连续子序列的和

 int sum(int idx){

     int ret = ;

     while (idx > ){

         ret += bit[idx];

         if (ret >= MOD){

             ret %= MOD;

         }

         idx -= lowBit(idx);

     }

     return ret;

 }

 int main(){

     int n, d, len;

     while (~scanf("%d%d", &n, &d)){

         for (int i = ; i <= n; i++){

             scanf("%d", &a[i]);

         }

         copy(a + , a +  + n, order + );

         sort(order + , order +  + n);

         len = unique(order + , order +  + n) - order - ;

         memset(bit, , sizeof(bit));

         for (int i = ; i <= n; i++){

             int r = upper_bound(order + , order +  + len, a[i] + d) - order - ;

             int l = lower_bound(order + , order +  + len, a[i] - d) - order - ;

             int p = lower_bound(order + , order +  + len, a[i]) - order;

             int temp = sum(r) - sum(l);

             temp = (temp % MOD + MOD) % MOD;

             update(p, len, temp + );

         }

         printf("%d\n", ((sum(len) - n) % MOD + MOD) % MOD);

     }

     return ;

 }

巴特西

hdu3450

最新文章

热门文章