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
      ; } 
     
    
   
  

?