题意：
给定一数列，问最多存在多少完美子序列。完美子序列定义如下：
原序列一共有2的n次方个子序列，这些子序列满足这样的关系：子序列元素个数至少2个，且任意相邻的两个元素之差不超过d。
题解：
每次新来一个元素x，都要去前面扫描有y个大于等于x-d且小于等于x+d的元素，然后以他们为结尾的完美序列数量的和+1（前面都不选），即为新来x结尾的完美序列。对于所有的x线性扫描可得出答案。数量的和当然是用树状数组快速完成。
另外：数大，量小，离散化。
#include<bits/stdc++.h>using namespace std;
const int maxn=1e6+100;
const int mod = 9901;
int c[maxn];
int a[maxn],b[maxn];int lowbit(int x)
{return x & -x;
}int sum(int x)
{int res=0;while(x>0){res=(res+c[x])%mod;x -= lowbit(x);}return res;
}void add(int x,int v)
{while(x<maxn){c[x] = (c[x]+v)%mod;x += lowbit(x);}
}int main()
{int n,d;while(cin>>n>>d){ int ans=0;memset(c,0,sizeof c);for(int i=1;i<=n;i++){scanf("%d",a+i);b[i] = a[i];}sort(b+1,b+1+n);int m = unique(b+1,b+1+n)-b-1;for(int i=1;i<=n;i++){int l=lower_bound(b+1,b+1+m,a[i]-d)-b-1;///但可以保证l在范围内呢int r=lower_bound(b+1,b+1+m,a[i]+d)-b;///lower_bound 并不一定保证r一定在范围内，但r-1一定在int v=lower_bound(b+1,b+1+m,a[i])-b;if(r>m||b[r]>a[i]+d)r--;///检查r是否超出范围int dp=(sum(r) - sum(l)+mod)%mod;add(v,dp+1);ans=(ans+dp)%mod;}cout<<ans<<endl;}
}