思路：二分查找位置，之后是裸的树状数组。
#include<set> #include<map> #include<cmath> #include<queue> #include<cstdio> #include<vector> #include<string> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> #define pb push_back #define mp make_pair #define Maxn 100010 #define Maxm 200010 #define LL int #define Abs(x) ((x)>0?(x):(-x)) #define lson(x) (x<<1) #define rson(x) (x<<1|1) #define inf 100000 #define lowbit(x) (x&(-x)) #define clr(x,y) memset(x,y,sizeof(x)) #define Mod 9901 using namespace std; int val[Maxn],sorted[Maxn],n,cnt; LL C[Maxn]; void update(int pos,LL val) { int i; while(pos<=n){ C[pos]+=val; C[pos]%=Mod; pos+=lowbit(pos); } } LL Sum(int pos) { LL sum=0; while(pos){ sum+=C[pos]; pos-=lowbit(pos); sum%=Mod; } return sum; } int main() { int d,i,j; while(scanf("%d%d",&n,&d)!=EOF){ clr(C,0); for(i=1;i<=n;i++){ scanf("%d",val+i); sorted[i]=val[i]; } sort(sorted+1,sorted+n+1); cnt=1; for(i=2;i<=n;i++) if(sorted[i]!=sorted[cnt]) sorted[++cnt]=sorted[i]; int l,r,pos; LL ans=0,temp; pos=lower_bound(sorted+1,sorted+cnt+1,val[1])-sorted; update(pos,1); for(i=2;i<=n;i++){ temp=0; l=lower_bound(sorted+1,sorted+cnt+1,val[i]-d)-sorted; r=lower_bound(sorted+1,sorted+cnt+1,val[i]+d)-sorted; pos=lower_bound(sorted+1,sorted+cnt+1,val[i])-sorted; if(sorted[l]>=val[i]-d) l--; if(sorted[r]>val[i]+d||r>cnt) r--; LL rr=Sum(r); LL ll=Sum(l); temp+=(rr-ll+Mod); update(pos,temp+1); ans+=temp; ans%=Mod; } printf("%d ",ans%Mod); } return 0; }