HDU3450CountingSequences

题意：求个数大于等于2的序列，要求每相邻的两个的大于d,求满足的个数

思路：同样是树状数组的应用，跟前面两题类&＃20284;，求每次加入的a[i],先求范围在[a[i]-d,a[i]&＃43;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 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 scanf("%d",&arr[i]);
brr[i] = arr[i];
}
sort(brr,brr+n);
f[0] = brr[0];
for (int i = 1; i if (brr[i] != brr[i-1])
f[cnt++] = brr[i];
f[cnt++] = INF;
for (int i = 0; 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 < }
return 0;
}

HDU - 3450 Counting Sequences,布布扣,bubuko.com