?
题意就不说了； 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
; }
?