@[ICPC_CCPC](/user/1015395)
```cpp
#include<bits/stdc++.h>
using namespace std;
long long int n,c,a[200005],ans;
int main(){
cin>>n>>c;
for(int i=1;i<=n;i++){
cin>>a[i];
}
sort(a+1,a+n+1);
for(int i=1;i<=n;i++){
ans+=upper_bound(a+1,a+i+1,a[i]-c)-lower_bound(a+1,a+i+1,a[i]-c);
}
cout<<ans;
return 0;
}
```
求关
by zhouzihe @ 2023-06-15 18:36:44
@[zhouzihe](/user/798537) 已关，但是。我不想使用二分做。用map时间复杂度只有O(n)吧，但是2分是O(nlogn)
by ICPC_CCPC @ 2023-06-15 18:41:06
@[ICPC_CCPC](/user/1015395) map查询O(1)？啊这......
by __Dice__ @ 2023-06-15 18:47:14
《红黑树查询做到O1》（什么神奇数据结构）
by __Dice__ @ 2023-06-15 18:48:50
@[__l_z_c__](/user/675888) 这道题的时间复杂度是O(n),因为不是要遍历吗，如果用字典，这样说可以吗?所以能不能帮我看看哪里有问题啊？
by ICPC_CCPC @ 2023-06-15 18:51:04
@[ICPC_CCPC](/user/1015395) umap会被卡，有的时候还没map快
by __Dice__ @ 2023-06-15 19:24:47
@[ICPC_CCPC](/user/1015395) 结果cnt用longlong
by ifbluerain @ 2023-07-11 12:32:58