HDU 3450 Counting Sequences

Problem Description

For a set of sequences of integers｛a1，a2，a3，...an｝, we define a sequence｛ai1,ai2,ai3...aik｝in which 1<=i1<i2<i3<...<ik<=n, as the sub-sequence of ｛a1，a2，a3，...an｝. It is quite obvious that a sequence with the length n has 2^n sub-sequences. And for a sub-sequence｛ai1,ai2,ai3...aik｝，if it matches the following qualities: k >= 2, and the neighboring 2 elements have the difference not larger than d, it will be defined as a Perfect Sub-sequence. Now given an integer sequence, calculate the number of its perfect sub-sequence.

Input

Multiple test cases The first line will contain 2 integers n, d（2<=n<=100000，1<=d=<=10000000） The second line n integers, representing the suquence

Output

The number of Perfect Sub-sequences mod 9901

Sample Input

4 2

1 3 7 5

Sample Output

4

統計數組中的完美子序列，相鄰元素差不大于d的是完美子序列。

對原數組進行排序，目前加入的數字為x，則隻對接下來出現的在【x-d，x+d】範圍内的數有影響。

#include<iostream>  
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 100005;
const int base = 9901;
int n, f[4 * maxn], M, d, a[maxn], b[maxn], ans;

int sum(int x)
{
  int tot = 0;
  for (x += M; x; x >>= 1) tot = (tot + f[x]) % base;
  return tot;
}

void add(int l, int r, int y)
{
  for (l += M - 1, r += M + 1; l ^ r ^ 1; l >>= 1, r >>= 1)
  {
    if (~l & 1) f[l ^ 1] += y;
    if ( r & 1) f[r ^ 1] += y;
  }
}

int main()
{
  while (~scanf("%d%d", &n, &d))
  {
    for (ans = 0, M = 1; M < n; M += M);
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; b[i] = a[i++]) scanf("%d", &a[i]);
    sort(b + 1, b + n + 1);
    for (int i = 1; i <=n; i++)
    {
      int l = a[i] - d, r = a[i] + d, x = a[i];
      l = lower_bound(b + 1, b + n + 1, l) - b;
      r = upper_bound(b + 1, b + n + 1, r) - b - 1;
      x = lower_bound(b + 1, b + n + 1, x) - b;
      ans += x = sum(x);  ans %= base;
      add(l, r, x + 1);
    }
    cout << ans << endl;
  }
  return 0;
}