学步园

来源：http://acm.hdu.edu.cn/showproblem.php?pid=3450

题意：给一些数，问有多少集合，满足相邻的数之间的差的绝对值小于d。

思路：树状数组，找出上界和下界后，和HDU 2227 一样。找上界和下界的方法为二分。

代码：

#include <iostream>
#include <cstdio>
#include <string.h>
#include <algorithm>
using namespace std;

const int N = 100010;
const int mod = 9901;
struct dit{
	int id,value,xuhao;
}dd[N],tempdd[N];
int cnt[N],dp[N];
bool cmp(dit a,dit b){
	return a.value < b.value;
}
int binary_search(int x,int lp,int rp){
	int mid = 0,ans = 1;
	while(lp <= rp){
	   mid = (lp + rp) / 2;
	   if(tempdd[mid].value > x)
		   rp = mid - 1;
	   else{
		   ans = mid;
		   lp = mid + 1;
	   }
	}
	return ans;
}
int binary_search2(int x,int lp,int rp){
	int ans = 1;
	while(lp <= rp){
	   int mid = (lp + rp) / 2;
	   if(tempdd[mid].value >= x){
	      rp = mid - 1;
		  ans = mid;
	   }
	   else
		   lp = mid + 1;
	}
	return ans;
}
int lowbit(int x){
	return x & (-x);
}
int sum(int x){
	int s = 0;
	while(x > 0){
	   s += cnt[x];
	   if(s >= mod)
		   s = s % mod;
	   x -= lowbit(x);
	}
	return s;
}
void update(int x,int add){
	while(x < N){
	   cnt[x] += add;
	   if(cnt[x] >= mod)
		   cnt[x] = cnt[x] % mod;
	   x += lowbit(x);
	}
}
int Bin(int x,int lp,int rp){
	while(lp <= rp){
	   int mid = (lp + rp) >> 1;
	   if(tempdd[mid].value == x)
		   return mid;
	   else if(tempdd[mid].value < x)
		   lp = mid + 1;
	   else
		   rp = mid - 1;
	}
	return -1;
}
int main(){
	//freopen("1.txt","r",stdin);
	int n,d;
	while(scanf("%d%d",&n,&d) != EOF){
		memset(cnt,0,sizeof(cnt));
		memset(dp,0,sizeof(dp));
		for(int i = 1; i <= n; ++i){
		    scanf("%d",&dd[i].value);
			dd[i].id = i;
			tempdd[i] = dd[i];
		}
		sort(tempdd+1,tempdd+n+1,cmp);
		int k = tempdd[1].id;
		int total = 0;
		for(int i = 1; i <= n; ++i){
			if(tempdd[i].value != tempdd[i-1].value || i == 1){
			   tempdd[++total].value = tempdd[i].value;
			}
		}
		int ans = 0;
		for(int i = 1; i <= n; ++i){
			int id = Bin(dd[i].value,1,total);
		   int x = dd[i].value - d;
		   int y = dd[i].value + d;
		   int xid = 0,yid = 0;
		   xid = binary_search2(x,1,total);
		   yid = binary_search(y,1,total);
		   int s1 = (sum(yid) - sum(xid - 1));
		   if(s1 < 0)
			   s1 += mod;
		   if(s1 >= mod)
			   s1 = s1 % mod;
		   ans = ans + s1 + 1;
		   if(ans >= mod)
			   ans = ans % mod;
		   update(id,(s1 + 1)%mod);
		}
		printf("%d\n",((ans - n) % mod + mod ) % mod);
	}
	return 0;
}