題意就不說了; 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; }