题解 CF1045G 【AI robots】

大菜鸡fks · 2018-10-18 20:37:39 · 题解

可以把问题抽象为二维数点问题。查询一个点就是查询矩形左下角为(xi-ri,qi-k) 右上角为(xi+ri,qi+k)的矩形

考虑扫描线。因为坐标范围比较大，可以用动态开点线段树维护。

#include<cstdio>
#include<algorithm>
using namespace std;
inline int read(){int x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f;}
inline void write(int x){if (x<0) putchar('-'),x=-x; if (x>=10) write(x/10); putchar(x%10+'0');}
inline void writeln(int x){write(x); puts("");}
const int N=1e5+5,INF=1e9;
struct event{
    int h,id,opt;
}b[N*3];
int ans,root,tot,n,cnt,K,x[N],r[N],q[N];
inline void init(){
    n=read(); K=read();
    for (int i=1;i<=n;i++){
        x[i]=read(); r[i]=read(); q[i]=read();
        b[++tot]=(event){q[i]-K,i,1};
        b[++tot]=(event){q[i]+K,i,-1};
        b[++tot]=(event){q[i],i,0};
    }
}
inline bool cmp(event A,event B){
    return A.h<B.h||A.h==B.h&&A.opt>B.opt;
}
struct node{
    int sum,son[2];
}a[N*30];
int query(int k,int l,int r,int x,int y){
    if (!k) return 0;
    if (l==x&&r==y) return a[k].sum;
    int mid=(l+r)>>1;
    if (mid>=y) return query(a[k].son[0],l,mid,x,y);
        else if (mid<x) return query(a[k].son[1],mid+1,r,x,y);
            else return query(a[k].son[0],l,mid,x,mid)+query(a[k].son[1],mid+1,r,mid+1,y);
}
void update(int &k,int l,int r,int x,int v){
    if (!k) k=++cnt; a[k].sum+=v;
    if (l==r) {a[k].sum+=v; return;}
    int mid=(l+r)>>1;
    if (mid>=x) update(a[k].son[0],l,mid,x,v); else update(a[k].son[1],mid+1,r,x,v);
}
inline void solve(){
    sort(b+1,b+1+tot,cmp);
    for (int i=1;i<=tot;i++){
        if (b[i].opt==-1) update(root,1,INF,x[b[i].id],-1);
        if (b[i].opt==0) ans+=query(root,1,INF,x[b[i].id]-r[b[i].id],x[b[i].id]+r[b[i].id])-1;
        if (b[i].opt==1) update(root,1,INF,x[b[i].id],1);
    }
    ans/=2;
    writeln(ans);
}
int main(){
    init(); solve();
    return 0;
}