我们按x排序,这样 |x1-x2|的绝对值就可以消掉了,然后我们讨论 |y1-y2| 的情况,很明显该式只有两种结果,即 y1-y2 或 y2-y1 ,并且二者互为相反数.
那么我们会发现,如果 dx = |x1-x2|,
若 dx >= d,则 这个点对的距离一定大于等于 d。
若 dx < d, 则 dx + y2-y1 和 dx + y1-y2 有且只有一个 值大于 d.
那我们不妨用两个线段树/ 树状数组来维护, 对于 第二种情况,分别计算 dx+y2-y1 >= d 和 dx + y1-y2 >= d 个数.
第一种情况每次加上即可
#include <iostream> #include <cstdio> #include <algorithm> #include <queue> #include <stack> #include <bitset> #include <vector> #include <map> #include <string> #include <cstring> #define fir first #define sec second using namespace std; typedef pair<int,int> P; const int maxn = 1e5+7; const int MAXN = 3e5+7; const int base = 1e5+7; P s[maxn]; int c1[MAXN],c2[MAXN]; bool cmp(const P& a,const P& b) { return a.fir< b.fir; } int lowbit(int x) {return x&-x;} void update(int x,int pos,int d) { while(pos<=MAXN-1) { if(x == 1)c1[pos] += d; else c2[pos] += d; pos += lowbit(pos); } return ; } int getsum(int x,int pos) { int res = 0; pos = min(pos,MAXN-1); while(pos>0) { if(x == 1) res += c1[pos]; else res += c2[pos]; pos -= lowbit(pos); } return res; } int main() { int n,d,l; scanf("%d%d%d",&n,&d,&l); for(int i=0;i<n;i++) { scanf("%d%d",&s[i].fir,&s[i].sec); } sort(s,s+n,cmp); int now = 0; long long res = 0; long long ans = 0; for(int i=0;i<n;i++) { while(now<i && s[i].fir-s[now].fir >= d) { update(1,-s[now].fir+s[now].sec+base,-1); update(2,-s[now].fir-s[now].sec+base,-1); res ++; now ++; } ans += res; long long x1 = d - (s[i].fir-s[i].sec) + base; long long x2 = d - (s[i].fir+s[i].sec) + base; ans += getsum(1,MAXN-1) - getsum(1,x1-1) + getsum(2,MAXN-1) - getsum(2,x2-1); update(1,-s[i].fir+s[i].sec+base,1); update(2,-s[i].fir-s[i].sec+base,1); //cout<<i<<' '<<ans<<endl; } printf("%lld\n",ans); return 0; }