线段树动态开点——cf1045G

#include<bits/stdc++.h>
using namespace std;
#define maxn 100005
#define INF 1000000005 
#define ll long long 
map<int,int>mp;//每个q开的线段树 
int n,K;
struct Node{int x,r,q;}p[maxn];
int cmp(Node a,Node b){return a.r>b.r;}

int size;
struct Seg{int lc,rc,sum;}T[maxn*50];
void update(int pos,int l,int r,int &rt){
    if(rt==0)rt=++size;
    T[rt].sum++;
    if(l==r)return;
    int mid=l+r>>1;
    if(pos<=mid)update(pos,l,mid,T[rt].lc);
    else update(pos,mid+1,r,T[rt].rc);
}
int query(int x,int L,int R,int l,int r){
    if(x==0)return 0;
    if(L<=l && R>=r)return T[x].sum;
    int mid=l+r>>1,res=0;
    if(L<=mid)res+=query(T[x].lc,L,R,l,mid);
    if(R>mid)res+=query(T[x].rc,L,R,mid+1,r);
    return res;
}

int main(){
    cin>>n>>K;
    for(int i=1;i<=n;i++)
        cin>>p[i].x>>p[i].r>>p[i].q;        
    ll res=0;
    sort(p+1,p+1+n,cmp);
    for(int i=1;i<=n;i++){
        for(int j=p[i].q-K;j<=p[i].q+K;j++)
            res=res+query(mp[j],p[i].x-p[i].r,p[i].x+p[i].r,-INF,INF);
        update(p[i].x,-INF,INF,mp[p[i].q]);
    }
    cout<<res<<endl;
}