Reference：http://www.cnblogs.com/wuyiqi/archive/2012/03/28/2420916.html
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=2836
题目大意：计算序列有多少种组合，每个组合至少两个数，使得组合中相邻两个数之差不超过H，序列有重复的数。MOD 9901。
解题思路：
朴素O（n^2)
以样例1 3 7 5为例，如果没有重复的数。
设dp[i]前n个数的方案数，初始化为1。
那么for(1…i…N)
$dp[i]=\sum dp[j]+1\quad,where \quad \left |num[i]-num[j] \right|<=H$
+1是为了计算两个点直接连接的情况，如样例：
dp[1]=1 （无连接）
dp[2]=dp[1]+1=2 （1-3连接）
dp[3]=1 (无连接）
dp[4]=dp[2]+dp[3]+1=4（1-3-5, 3-5，7-5）
如果没有+1，那么就没法dp下去，同时，这样每个点多算了1，所以ans=1+2+1+4-4=4
快速求和优化
上面O（n^2)的原因在于, 原始序列的dp区间不是连续的，比如1,3,8,3,5,7 H=2
5的dp区间可以是2,4，需要多扫一轮来找出这些离散的值。
实际上，dp过程中可以不依赖原始序列顺序。将原始序列排序离散化去重后，变成1,3,5,8
这样，新添加一个box的时候，可以二分找其值在新序列中边界L，R，这样，原本的离散dp求和，
被转化成了连续区间求和$\sum sum(R)-sum(L-1)$
原因很简单，5在实际计算时，在3,3,7中都被牵扯到，是一个对称计算。所以排序去重后可以简化为对连续区间的计算。
至于为什么要去重，主要是为了解决重值的重复计算（原题并没有说没有重值）
比如1,3,3，如果不去重，为第二个3单独开个dp状态，那么1-3被算了两次（dp初始值为1）
所以第二个3，无须再开一个dp状态，直接第一个3基础上算就行了。保证ans-n是最后的结果。
代码
#include "cstdio"
#include "algorithm"
#include "cstring"
using namespace std;
#define maxn 100005
#define mod 9901
int num[maxn],Hash[maxn],n,h,s[maxn];
int lowbit(int x) {return x&(-x);}
int sum(int x)
{
int ret=;
while(x>) ret=(ret+s[x])%mod,x-=lowbit(x);
return ret%mod;
}
void update(int x,int d)
{
while(x<=n) s[x]=(s[x]+d)%mod,x+=lowbit(x);
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&n,&h)!=EOF)
{
memset(Hash,,sizeof(Hash));
memset(s,,sizeof(s));
for(int i=;i<=n;i++)
{
scanf("%d",&num[i]);
Hash[i]=num[i];
}
sort(Hash+,Hash+n+);
int diff=unique(Hash+,Hash+n+)-Hash-;
int ans=;
for(int i=;i<=n;i++)
{
int idx=lower_bound(Hash+,Hash+diff+,num[i])-Hash;
int L=lower_bound(Hash+,Hash+diff+,num[i]-h)-Hash;
int R=upper_bound(Hash+,Hash+diff+,num[i]+h)-Hash-;
int dp=(sum(R)-sum(L-)+)%mod;
ans+=dp;
update(idx,dp);
}
printf("%d\n",(ans-n)%mod);
}
}
