题面：
https://www.luogu.org/problemnew/show/P2093
https://darkbzoj.cf/problem/2626
思路：
算是kd-tree裸题，对于查询的数维护含k个数的小根堆，这个堆中装的是距离最大的k个数
WA了挺久，有一些情况要注意
1.堆中存放的要是一个结构体，bh为编号，val为距离，只能定义 ' < '，且默认大根堆，我们不妨反过来定义，详情见程序
2.p[i]虽然一开始是有序的，但建树的时候就把顺序打乱了，不能轻易认为p[i]中的i就是第i个节点，要再保存一个p[i].bh记录的才是编号
3.本来query中是否向儿子管辖区域找我写的是val>=即可，结果TLE，所以要优化一下，顶一个数组mbh[i]，存管辖范围内最小编号，用法参照mn[i],mx[i]
#include<bits/stdc++.h> #define lc (ch[x][0]) #define rc (ch[x][1]) #define ll long long using namespace std; const int maxn=1e6+4; int n,m; ll mn[maxn][2],mx[maxn][2],ch[maxn][2],mbh[maxn]; int nthdir; struct node{int bh;ll val;bool operator < (const node &no) const{if(no.val==val) return bh<no.bh;return val>no.val;}node(int x,long long y){bh=x;val=y;} }; priority_queue<node>q; inline ll sq(ll x){return (ll)x*x; } struct Point{ll pos[2];int bh;ll& operator [](int x){return pos[x];}bool operator < (const Point &t) const {return pos[nthdir] < t.pos[nthdir];}ll operator - (const Point &t) const {return (ll)sq(pos[0]-t.pos[0])+(ll)sq(pos[1]-t.pos[1]);}Point(ll x,ll y,int b){pos[0]=x;pos[1]=y;bh=b;}Point(){}; }p[maxn]; inline void pushup(int x){for(int i=0;i<=1;i++){mn[x][i]=mx[x][i]=p[x][i];mbh[x]=p[x].bh;if(lc){mn[x][i]=min(mn[x][i],mn[lc][i]);mx[x][i]=max(mx[x][i],mx[lc][i]);mbh[x]=min(mbh[x],mbh[lc]);}if(rc){mn[x][i]=min(mn[x][i],mn[rc][i]);mx[x][i]=max(mx[x][i],mx[rc][i]);mbh[x]=min(mbh[x],mbh[rc]);}} } inline int build(int l,int r,int dir){nthdir=dir;int x=(l+r)>>1;nth_element(p+l,p+x,p+r+1);if(l<x) lc=build(l,x-1,dir^1);if(r>x) rc=build(x+1,r,dir^1);pushup(x);return x; } inline ll calc(int x,Point P){return max((ll)sq(mn[x][0]-P[0]),(ll)sq(mx[x][0]-P[0]))+max((ll)sq(mn[x][1]-P[1]),(ll)sq(mx[x][1]-P[1])); } inline void query(int x,Point P){ll h=P-p[x];if(node(p[x].bh,h) < q.top()){q.pop();q.push(node(p[x].bh,h));}ll l=-(maxn<<1),r=-(maxn<<1);if(lc) l=calc(lc,P);if(rc) r=calc(rc,P);if(l>r){if(node(mbh[lc],l)<q.top()) query(lc,P);if(node(mbh[rc],r)<q.top()) query(rc,P);//上面和下面这两组语句等价 //if(q.top().val<l||(q.top().val==l&&q.top().bh>mbh[lc])) query(lc,P);//if(q.top().val<r||(q.top().val==r&&q.top().bh>mbh[rc])) query(rc,P);}else{if(node(mbh[rc],r)<q.top()) query(rc,P);if(node(mbh[lc],l)<q.top()) query(lc,P);//if(q.top().val<r||(q.top().val==r&&q.top().bh>mbh[rc])) query(rc,P);//if(q.top().val<l||(q.top().val==l&&q.top().bh>mbh[lc])) query(lc,P); } } int main(){memset(mn,0x3f,sizeof(mn));memset(mx,0xc0,sizeof(mx));scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%lld%lld",&p[i][0],&p[i][1]),p[i].bh=i;int rt=build(1,n,0);scanf("%d",&m);while(m--){int x,y,k;scanf("%lld%lld%d",&x,&y,&k);while(!q.empty()) q.pop();for(int i=1;i<=k;i++) q.push(node(0,-maxn));query(rt,Point(x,y,0));printf("%d\n",(q.top()).bh);}return 0; }