刚学OI的萌新求助KD-Tree近邻查询

#include <iostream>
#include <cstdio>
#include <math.h>
#include <algorithm>
#include <istream>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <string.h>
#include <map>
#include <unordered_map>
#include <random>
#include <bitset>
#define int long long
//#define double long double
#define p1(x) x.first
#define p2(x) x.second
#define i128  __int128_t
//#pragma GCC optimize(2)
#define w(x) t[x].w
#define sw(x) t[x].sw
#define siz(x) t[x].siz
#define lc(x) t[x].c[0]
#define rc(x) t[x].c[1]
#define d(x) t[x].d
#define pii pair<int,int>
//若汁记好了以后再用Ctrl+C/+V你就是狗
using namespace std;
const int INF=2e18+7;
const double alpha=0.7;
struct node{
    int mxx,mxy;
    int mnx,mny;
    int x,y;
    int w,sw;
    int siz;
    bool d;
    int c[2];
    inline int mxd(int x,int y){
        int dx=max(x-mnx,mxx-x),dy=max(y-mny,mxy-y);
        return dx*dx+dy*dy;
    }
    inline int mnd(int x,int y){
        int dx=min(max(0ll,mnx-x),max(0ll,x-mxx)),dy=min(max(0ll,mny-y),max(0ll,y-mxy));
        return dx*dx+dy*dy;
    }
    inline int dt(int px,int py){
        int dx=(px-x),dy=py-y;
        return dx*dx+dy*dy;
    }
}t[200300];
inline void upd(int x){
    t[x].mxx=max(t[x].x,max(t[lc(x)].mxx,t[rc(x)].mxx));
    t[x].mxy=max(t[x].y,max(t[lc(x)].mxy,t[rc(x)].mxy));
    t[x].mnx=min(t[x].x,min(t[lc(x)].mnx,t[rc(x)].mnx));
    t[x].mny=min(t[x].y,min(t[lc(x)].mny,t[rc(x)].mny));
    siz(x)=siz(lc(x))+siz(rc(x))+1;
    sw(x)=sw(lc(x))+sw(rc(x))+w(x);
    
}
int cnt,rt;
inline int nnd(int x,int y,int w,bool d){
    t[++cnt]={x,y,x,y,x,y,w,w,1,d};;
    return cnt;
}
int ct;
int p[200300];
inline void trs(int x){
    p[++ct]=x;
    if(lc(x))trs(lc(x));
    if(rc(x))trs(rc(x));
}
inline bool cmpx(int a,int b){
    return t[a].x<t[b].x;
}
inline bool cmpy(int a,int b){
    return t[a].y<t[b].y;
}
inline int rb(int l,int r,bool d){
    if(r<l)return 0;
    if(l==r){
        lc(p[l])=rc(p[l])=0;
        siz(p[l])=1;
        d(p[l])=d;
        sw(p[l])=w(p[l]);
        upd(p[l]);
        return p[l];
    }
    int mid=l+r>>1;
    nth_element(p+l,p+mid,p+r,d?cmpx:cmpy);
    lc(p[mid])=rb(l,mid-1,!d);
    rc(p[mid])=rb(mid+1,r,!d);
    d(p[mid])=d;
    upd(p[mid]);
    return p[mid];
}
inline void RB(int &x){
        ct=0;
        trs(x);
        int d=d(x);
        x=rb(1,ct,d);
}
inline void chk(int &x){
    if(max(siz(lc(x)),siz(rc(x)))>=siz(x)*alpha)RB(x);
}
inline void ins(int &x,int px,int py,int w,int d){
    if(!x){
        x=nnd(px,py,w,d);
        return ;
    }
    if(d){
        if(px<=t[x].x)ins(lc(x),px,py,w,!d);
        else ins(rc(x),px,py,w,!d);
    }
    else{
        if(py<=t[x].y)ins(lc(x),px,py,w,!d);
        else ins(rc(x),px,py,w,!d);
    }
    upd(x);
    chk(x);
}
inline int g(int x,int lx,int ly,int rx,int ry){
    if(!x)return 0;
    if(rx>=t[x].mxx&&ry>=t[x].mxy&&lx<=t[x].mnx&&ly<=t[x].mny)return sw(x);
    int res=0;
    if(rx>=t[x].x&&ry>=t[x].y&&lx<=t[x].x&&ly<=t[x].y)res=w(x);
    if(d(x)){
        if(lx<=t[lc(x)].mxx)res+=g(lc(x),lx,ly,rx,ry);
        if(rx>=t[rc(x)].mnx)res+=g(rc(x),lx,ly,rx,ry);
    }
    else{
        if(ly<=t[lc(x)].mxy)res+=g(lc(x),lx,ly,rx,ry);
        if(ry>=t[rc(x)].mny)res+=g(rc(x),lx,ly,rx,ry);
    }
    return res;
}
priority_queue<pii,vector<pii>,greater<pii>>qmx;
priority_queue<pii>qmn;
inline void setmx(int k){
    while(!qmx.empty())qmx.pop();
    for(int i=1;i<=k;i++)
        qmx.push({-INF,0});
}
inline void setmn(int k){
    while(!qmn.empty())qmn.pop();
    for(int i=1;i<=k;i++)
        qmn.push({INF,0});
}
inline void gmx(int x,int px,int py){
    if(!x)return ;
    if(t[x].mxd(px,py)<=p1(qmx.top()))return ;
    qmx.push({t[x].dt(px,py),-x});
    qmx.pop();
    gmx(lc(x),px,py);
    gmx(rc(x),px,py);
}
inline void gmn(int x,int px,int py){
    if(!x)return ;
    if(t[x].mnd(px,py)<=p1(qmn.top()))return ;
    qmn.push({t[x].dt(px,py),-x});
    qmn.pop();
    gmn(lc(x),px,py);
    gmn(rc(x),px,py);
}
int n,q;
signed main(){
    ios::sync_with_stdio(0);
//    freopen("","r",stdin);
//    freopen("","w",stdout);
    t[0]={-INF,-INF,INF,INF,0,0,0,0,0};
    cin>>n;
    for(int i=1;i<=n;i++){
        int x,y;
        cin>>x>>y;
        ins(rt,x,y,0,d(rt));
    }RB(rt);
    cin>>q;
    while(q--){
        int px,py,k;
        cin>>px>>py>>k;
        setmx(k);
        gmx(rt,px,py);
        cout<<-p2(qmx.top())<<endl;
    }
    return 0;
}