HDU - 3450 Counting Sequences

題意：求個數大於等於2的序列，要求每相鄰的兩個的大於d,求滿足的個數

思路：同樣是樹狀數組的應用，跟前面兩題類似，求每次加入的a[i],先求范圍在[a[i]-d,a[i]+d]的個數，再加到a[i]上，加一加的是本身，還有要注意的是，要減去1個的情況，跟前面兩題不一樣，

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 100005;
const int MOD = 9901;

int n,arr[MAXN],k;
int brr[MAXN],cnt,f[MAXN];
int crr[MAXN];

int lowbit(int x){
	return x&(-x);
}

void update(int x,int d){
	while (x < MAXN){
		crr[x]  = (crr[x]+d) % MOD;
		x += lowbit(x);
	}
}

int sum(int x){
	int ans = 0;
	while (x > 0){
		ans = (ans + crr[x])%MOD;
		x -= lowbit(x);
	}
	return ans;
}

int main(){
	while (scanf("%d%d",&n,&k) != EOF){
		cnt = 1;
		memset(crr,0,sizeof(crr));
		for (int i = 0; i < n; i++){
			scanf("%d",&arr[i]);
			brr[i] = arr[i];
		}
		sort(brr,brr+n);
		f[0] = brr[0];
		for (int i = 1; i < n; i++)
			if (brr[i] != brr[i-1])
				f[cnt++] = brr[i];
		f[cnt++] = INF;	
		for (int i = 0; i < n; i++){
			int x = lower_bound(f,f+cnt,arr[i]) - f + 1;
			int y = upper_bound(f,f+cnt,arr[i]+k) - f;
			int z = lower_bound(f,f+cnt,arr[i]-k) - f + 1;
			int val = sum(y) - sum(z-1) + 1;
			val = (val%MOD+MOD) % MOD;
			update(x,val);
		}
		int ans = sum(cnt);
		ans = ((ans-n)%MOD+MOD)%MOD;
		cout << ans << endl;
	}
	return 0;
}