原题大意

每个点有三个属性，x，r，f；统计有多少对点i，j满足 min(ri,rj) >= |xi-xj| 且 |fi-fj| <=k，这样的点对被称作是“坏的”。

算法分析

考虑到min(ri, rj)这个条件比较烦，把点按r从大到小排序。排序后，对于第i个点，它和之前的第j个点组成bad pair的充要条件为|xi-xj|<=ri && |fi-fj|<=k。整理一下，变成xi-ri<=xj<=xi+ri && -k+fi<=fj<=k+fi。这其实就是按顺序在平面上插入点，并查询给定矩形区域内点的个数，是经典的三维偏序问题，用CDQ分治即可解决。

http://blog.csdn.net/jtjy568805874/article/details/50638665

http://www.cnblogs.com/mlystdcall/p/6351344.html

程序代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

struct que{
    int r, x, f, type, id;//这里的type是对查询结果的贡献，下面规定的-1和1类似于求概率（P(AUB)=P(A)+P(B)-P(AB)）
}a[505000], b[505000];
int n, k;
int c[20500];//树状数组
ll ans=0;

//因为是一个点一个点的考虑，所以要排序，并且处理相同情况
bool cmp(que a, que b){
    if(a.r!=b.r)return a.r>b.r;
    if(a.id!=b.id)return a.id<b.id;//这里的顺序只是为了确保由一个点产生的5个点连续，大于小于无所谓

    return abs(a.type)>abs(b.type);
}

bool cmp1(que a, que b){
    return a.x<b.x;
}

int lowbit(int x){
    return x&(-x);
}

//树状数组的更新
void update(int x){
    while(x<=20000){
        c[x]++;
        x+=lowbit(x);
    }
}
//树状数组求前缀和
int query(int x){
    int sum=0;
    while(x){
        sum+=c[x];
        x-=lowbit(x);
    }
    return sum;
}

void reset(int x){
    while(x<=20000){
        c[x]=0;
        x+=lowbit(x);
    }
}

void cdq(int l, int r){
    if(l==r)return;
    int m=(l+r)/2;
    cdq(l, m);
    cdq(m+1, r);
    for(int i=l;i<=r;i++)b[i]=a[i];
    sort(b+l, b+m+1, cmp1);
    sort(b+m+1, b+r+1, cmp1);
    int j=l;
    for(int i=m+1;i<=r;i++){
        while(j<=m&&b[j].x<=b[i].x){
            if(!b[j].type)update(b[j].f);
            j++;
        }
        ans+=b[i].type*query(b[i].f);
    }
    for(int i=l;i<=m;i++){
        reset(b[i].f);
    }
    return;
}

int main()
{
    scanf("%d%d", &n, &k);
    for(int i=0;i<n;i++){
        int r, x, f;
        scanf("%d%d%d", &x, &r, &f);
        a[5*i]=(que){r, x+r, f+k+20, 1, i};
        a[5*i+1]=(que){r, x-r-1, f+k+20, -1, i};
        a[5*i+2]=(que){r, x+r, f-k-1+20, -1, i};
        a[5*i+3]=(que){r, x-r-1, f-k-1+20, 1, i};
        a[5*i+4]=(que){r, x, f+20, 0, i};
    }
    //f+20是防止在树状数组统计时会出现负的，type为0，是因为这个点本身有没有贡献没有意义。
    sort(a, a+5*n, cmp);
    memset(c, 0, sizeof(c));
    cdq(0, 5*n-1);
    printf("%lld\n", ans);
}