这个题的灵感来自与前几天做的一个题，思路想好之后，忽然发现自己好想会做这类题目了，不过还是要折腾老久，因为好多细节处理不好。 wa了好多好多次了，终于加了个mod就过了，尼玛。。。。。。 [code lang="cpp"] i64 query(int pos) { i64 sum = 0 ; while(pos > 0 ) { sum += f[pos] %mod; pos -= lowbit(pos); } return sum; } void update(int pos,i64 val) { while(pos <= nn) { f[pos] += val % mod; pos += lowbit(pos); } } int main() { while(scanf("%d%d",&n,&d)!=EOF) { nn1 = 0 ; for(int i = 0 ; i < n ; i++) { RD(a[i]); d1[nn1 ++ ] = a[i]; d1[nn1 ++ ] = a[i] - d - 1; d1[nn1 ++ ] = a[i] + d; } sort(d1,d1+nn1); nn = 0; for(int i=1; i<nn1; i++) if(d1[i] != d1[nn]) d1[++nn] = d1[i]; for(int i=0; i<n; i++) { pos[i] = lower_bound(d1,d1+nn,a[i]) - d1 + 1; } clr(f,0); clr(dp,0); for(int i=0; i<n; i++) { int pos1,pos2; i64 tmp1,tmp2,tmp; pos1 = lower_bound(d1,d1+nn,a[i] + d ) - d1 + 1; pos2 = lower_bound(d1,d1+nn,a[i] - d - 1 ) - d1 + 1; tmp = query(pos1) - query(pos2) + mod + mod ; dp[pos[i]] += tmp % mod; update(pos[i],(tmp + 1) % mod ); } i64 ans ; ans = 0; for(int i=1 ; i<=nn; i++) ans += dp[i] % mod; PR(ans%mod); } return 0; } [/code]