Counting Sequences
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 5Sample Output
4设dp[i]以i为结尾的满足条件的子序列个数
dp[v]=sum(dp[u])+1(u<=v 并且|u-v|<=d)
可以用树状数组快速维护[i-d,i+d]内的数的个数
注意离散化和二分查找数据
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; int n,d; #define maxn 100005 const ll mod=1e9+7; int c[maxn]; int a[maxn]; int b[maxn]; int lowbit(int x) { return x&(-x); } int sum(int i) { int res=0; while(i>0) { res+=c[i]; i-=lowbit(i); } return res; } void update(int i,int val) { while(i<=maxn) { c[i]+=val; i+=lowbit(i); } } int main() { while(~scanf("%d%d",&n,&d)) { memset(c,0,sizeof(c)); for(int i=1;i<=n;i++) {scanf("%d",&a[i]); b[i]=a[i]; } sort(b+1,b+n+1); int len=unique(b+1,b+n+1)-b-1; ll ans=0; ll res=0; for(int i=1;i<=n;i++) { int pos1=upper_bound(b+1,b+len+1,a[i]+d)-b-1; int pos2=lower_bound(b+1,b+len+1,a[i]-d)-b; int pos=lower_bound(b+1,b+len+1,a[i])-b; res=(sum(pos1)%mod-sum(pos2-1)%mod+mod)%mod; ans=(ans%mod+res%mod)%mod; update(pos,res+1); } printf("%lld\n",ans); } return 0; }
