更新日志
思路
对于每一个点都求一边其最短距离，最后统计。
详细地，对于每个区间，先与其中点判断并更新距离（注意特判不能是同一点），然后找出在这一节点排序维度上，查询点到中点距离，记作 \(D\)。
看查询点在中点左侧/右侧，判断去左右区间。（在这一节点排序的维度上。）
同侧更新完之后，如果一侧的答案要大于当前点到中点的一维距离，就说明答案的另一点可能在另一侧，再查询另一侧的子区间。
模板
struct node{
int id;
ll v[K];
int lson,rson;
}ns[N];
int n;
int ak;
bool cmp(node a,node b){return a.v[ak]<b.v[ak];}
ll dis(int a,int b){
ll res=0;
for(int k=0;k<K;k++){
res+=(ns[a].v[k]-ns[b].v[k])*(ns[a].v[k]-ns[b].v[k]);
}
return res;
}
ll dis(int a,int b,int k){
return (ns[a].v[k]-ns[b].v[k])*(ns[a].v[k]-ns[b].v[k]);
}
int mp[N];
struct kdtree{
int build(int l,int r,int k=0){
int m=l+r>>1;
ak=k;nth_element(ns+l,ns+m,ns+r+1,cmp);
mp[ns[m].id]=m;
if(l<m)ns[m].lson=build(l,m-1,(k+1)%K);
if(m<r)ns[m].rson=build(m+1,r,(k+1)%K);
return m;
}
ll query(int q,int x,int k=0){
ll res=INF,tes=INF;
if(x!=q)res=min(res,dis(x,q));
tes=dis(x,q,k);
if(ns[q].v[k]<=ns[x].v[k]){
if(ns[x].lson)res=min(res,query(q,ns[x].lson,(k+1)%K));
if(tes<res&&ns[x].rson)res=min(res,query(q,ns[x].rson,(k+1)%K));
}else{
if(ns[x].rson)res=min(res,query(q,ns[x].rson,(k+1)%K));
if(tes<res&&ns[x].lson)res=min(res,query(q,ns[x].lson,(k+1)%K));
}
return res;
}
}kdt;
例题
代码
前注：就是模板。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef double db;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<int,ll> pil;
typedef pair<ll,int> pli;
template <typename Type>
using vec=vector<Type>;
template <typename Type>
using grheap=priority_queue<Type>;
template <typename Type>
using lrheap=priority_queue<Type,vector<Type>,greater<Type> >;
#define fir first
#define sec second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define dprint(x) cout<<#x<<"="<<x<<"\n";
const int inf=0x3f3f3f3f;
const ll INF=4e18;
const int mod=1e9+7/*998244353*/;
const int N=1e5+5,K=2;
struct node{
int id;
ll v[K];
int lson,rson;
}ns[N];
int n;
int ak;
bool cmp(node a,node b){return a.v[ak]<b.v[ak];}
ll dis(int a,int b){
ll res=0;
for(int k=0;k<K;k++){
res+=(ns[a].v[k]-ns[b].v[k])*(ns[a].v[k]-ns[b].v[k]);
}
return res;
}
ll dis(int a,int b,int k){
return (ns[a].v[k]-ns[b].v[k])*(ns[a].v[k]-ns[b].v[k]);
}
int mp[N];
struct kdtree{
int build(int l,int r,int k=0){
int m=l+r>>1;
ak=k;nth_element(ns+l,ns+m,ns+r+1,cmp);
mp[ns[m].id]=m;
if(l<m)ns[m].lson=build(l,m-1,(k+1)%K);
if(m<r)ns[m].rson=build(m+1,r,(k+1)%K);
return m;
}
ll query(int q,int x,int k=0){
ll res=INF,tes=INF;
if(x!=q)res=min(res,dis(x,q));
tes=dis(x,q,k);
if(ns[q].v[k]<=ns[x].v[k]){
if(ns[x].lson)res=min(res,query(q,ns[x].lson,(k+1)%K));
if(tes<res&&ns[x].rson)res=min(res,query(q,ns[x].rson,(k+1)%K));
}else{
if(ns[x].rson)res=min(res,query(q,ns[x].rson,(k+1)%K));
if(tes<res&&ns[x].lson)res=min(res,query(q,ns[x].lson,(k+1)%K));
}
return res;
}
}kdt;
void solve(){
cin>>n;
for(int i=1;i<=n;i++){
ns[i].id=i;
cin>>ns[i].v[0]>>ns[i].v[1];
ns[i].lson=ns[i].rson=0;
}
int rt=kdt.build(1,n);
for(int i=1;i<=n;i++){
cout<<kdt.query(mp[i],rt)<<"\n";
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int t;cin>>t;
while(t--)solve();
return 0;
}