在竞赛中，kd-tree一般只用于平面，很少有高于二维的情况。
在随机情况下，kd-tree的复杂度为O(NlogN)，但会被极端数据卡到平方级别。
总而言之，就是优美的暴力。
查询时，通过估价函数进行减值。当然，这个函数一定要大于等于最后的结果，才有正确性。
1.求平面最近点对，欧几里得距离。精确到小数点后4位。
模板，不解释。
// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
const double eps=0.00001;
const double inf=1E18;
const int maxn=2E5+;
int n,m;
int son[maxn][],size;
double val[maxn][],minv[maxn][],maxv[maxn][],ans,v[];
struct pt{double v[];}a[maxn];
bool cmp0(pt x,pt y){return x.v[]<y.v[];}
bool cmp1(pt x,pt y){return x.v[]<y.v[];}
bool cmp2(pt x,pt y)
{
if(x.v[]==y.v[])return x.v[]<y.v[];
return x.v[]<y.v[];
}
inline void update(int x,int y)
{
for(int i=;i<;++i)
{
minv[x][i]=min(minv[x][i],minv[y][i]);
maxv[x][i]=max(maxv[x][i],maxv[y][i]);
}
}
void build(int l,int r,int dep,int num)
{
int mid=(l+r)>>;
if(dep%==)nth_element(a+l,a+mid,a+r+,cmp0);
else nth_element(a+l,a+mid,a+r+,cmp1);
minv[num][]=maxv[num][]=val[num][]=a[mid].v[];
minv[num][]=maxv[num][]=val[num][]=a[mid].v[];
if(l<=mid-)
{
build(l,mid-,dep+,son[num][]=++size);
update(num,son[num][]);
}
if(mid+<=r)
{
build(mid+,r,dep+,son[num][]=++size);
update(num,son[num][]);
}
}
inline double s(double x){return x*x;}
inline double dis(int x,double v[]){return s(val[x][]-v[])+s(val[x][]-v[]);}
inline double f(int x,double v[])
{
double sum=;
for(int i=;i<;++i)
{
if(minv[x][i]>v[i])sum+=s(minv[x][i]-v[i]);
if(maxv[x][i]<v[i])sum+=s(maxv[x][i]-v[i]);
}
return sum;
}
void ask(double v[],double&ans,int num)
{
if(!num)return;
double d=dis(num,v);
if(d>=eps)ans=min(ans,d);
double lf=f(son[num][],v),rf=f(son[num][],v);
if(lf<rf)
{
if(lf<ans)ask(v,ans,son[num][]);
if(rf<ans)ask(v,ans,son[num][]);
}
else
{
if(rf<ans)ask(v,ans,son[num][]);
if(lf<ans)ask(v,ans,son[num][]);
}
}
int main()
{
ios::sync_with_stdio(false);
cin>>n;
for(int i=;i<=n;++i)cin>>a[i].v[]>>a[i].v[];
build(,n,,size=);
sort(a+,a+n+,cmp2);
for(int i=;i<n;++i)
{
if(a[i].v[]==a[i+].v[]&&a[i].v[]==a[i+].v[])
{
cout<<"0.0000"<<endl;
return ;
}
}
ans=inf;
for(int i=;i<=n;++i)
{
v[]=a[i].v[];
v[]=a[i].v[];
ask(v,ans,);
}
cout<<fixed<<setprecision()<<sqrt(ans)<<endl;
return ;
}
https://www.luogu.org/problemnew/show/P1429
2.求平面最近点对，曼哈顿距离。
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int maxn=1E6+;
const int inf=INT_MAX;
int n,m,opt,ans;
int son[maxn][],val[maxn][],size,maxv[maxn][],minv[maxn][],v[];
struct pt{int v[];}a[maxn];
bool cmp0(pt x,pt y){return x.v[]<y.v[];}
bool cmp1(pt x,pt y){return x.v[]<y.v[];}
inline int read()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
}
void write(int x)
{
if(x<=){putchar(''+x);return;}
write(x/);
putchar(''+x%);
}
inline void update(int x,int y)
{
for(int i=;i<;++i)
{
minv[x][i]=min(minv[x][i],minv[y][i]);
maxv[x][i]=max(maxv[x][i],maxv[y][i]);
}
}
void build(int l,int r,int dep,int num)
{
int mid=(l+r)>>;
if(dep&)nth_element(a+l,a+mid,a+r+,cmp1);
else nth_element(a+l,a+mid,a+r+,cmp0);
maxv[num][]=minv[num][]=val[num][]=a[mid].v[];
maxv[num][]=minv[num][]=val[num][]=a[mid].v[];
if(l<=mid-)
{
build(l,mid-,dep+,son[num][]=++size);
update(num,son[num][]);
}
if(mid+<=r)
{
build(mid+,r,dep+,son[num][]=++size);
update(num,son[num][]);
}
}
void insert(int dep,int num)
{
if(v[dep&]<=val[num][dep&])
{
if(son[num][])insert(dep+,son[num][]);
else
{
son[num][]=++size;
maxv[size][]=minv[size][]=val[size][]=v[];
maxv[size][]=minv[size][]=val[size][]=v[];
}
update(num,son[num][]);
}
else
{
if(son[num][])insert(dep+,son[num][]);
else
{
son[num][]=++size;
maxv[size][]=minv[size][]=val[size][]=v[];
maxv[size][]=minv[size][]=val[size][]=v[];
}
update(num,son[num][]);
}
}
inline int f(int x)
{
int sum=;
for(int i=;i<;++i)
{
if(minv[x][i]>v[i])sum+=minv[x][i]-v[i];
if(maxv[x][i]<v[i])sum+=v[i]-maxv[x][i];
}
return sum;
}
inline int dis(int x){return abs(val[x][]-v[])+abs(val[x][]-v[]);}
void ask(int&ans,int num)
{
if(num==)return;
ans=min(ans,dis(num));
int lf=f(son[num][]),rf=f(son[num][]);
if(lf<rf)
{
if(lf<ans)ask(ans,son[num][]);
if(rf<ans)ask(ans,son[num][]);
}
else
{
if(rf<ans)ask(ans,son[num][]);
if(lf<ans)ask(ans,son[num][]);
}
}
void out(int num,int dep)
{
if(num==)return;
cout.width(*dep);
cout<<val[num][]<<" "<<val[num][]<<endl;
out(son[num][],dep+);
out(son[num][],dep+);
}
int main()
{
ios::sync_with_stdio(false);
n=read();m=read();
for(int i=;i<=n;++i)a[i].v[]=read(),a[i].v[]=read();
build(,n,,size=);
while(m--)
{
opt=read(),v[]=read(),v[]=read();
if(opt==)insert(,);
else
{
ans=inf;
ask(ans,);
write(ans);
putchar('\n');
}
// out(1,0);
}
return ;
}
https://www.lydsy.com/JudgeOnline/problem.php?id=2648
洛咕上T了。
3.求平面最远点对。精确到小数点后4位。
换个估价函数就行了，没代码。
4.求平面上k远点对。给出距离的平方，n≤100,000，k≤100。
博主的做法类似于超级钢琴和异或粽子的做法，先将所有的点的最远距离加入大根堆，每次取出最大元素，更新其次大的答案。
在查询过程中，为了防止访问到之前的答案，hash一下。
不要偷懒用map。1.6s--->16s。
#include<bits/stdc++.h>
#define mod 10000007
#define p 13131
using namespace std;
typedef long long int ll;
const ll maxn=1E5+;
const ll inf=LONG_LONG_MAX; ll min(ll x,ll y){return x<y?x:y;}
ll max(ll x,ll y){return x>y?x:y;} int son[maxn][],n,k,m,size;
ll val[maxn][],maxv[maxn][],minv[maxn][],v[],ans,pos; struct p1{ll v[];}a[maxn];
bool vis[mod];
int M(int x,int y){return (x*p+y)%mod;}
bool cmp0(p1 x,p1 y){return x.v[]<y.v[];}
bool cmp1(p1 x,p1 y){return x.v[]<y.v[];}
struct pt{int pos;ll ans;};
struct _cmp{bool operator()(pt x,pt y)const{return x.ans<y.ans;}}; priority_queue<pt,vector<pt>,_cmp>Q; inline int read()
{
int w=,q=;
char c=getchar();
while((c<'' || c>'') && c!='-') c=getchar();
if (c=='-') q=, c=getchar();
while (c>='' && c<='') w=w*+c-'', c=getchar();
return q ? -w : w;
} void update(int x,int y)
{
for(int i=;i<;++i)
{
minv[x][i]=min(minv[x][i],minv[y][i]);
maxv[x][i]=max(maxv[x][i],maxv[y][i]);
}
}
void build(int l,int r,int dep,int num)
{
int mid=(l+r)>>;
if(dep&)nth_element(a+l,a+mid,a+r+,cmp0);
else nth_element(a+l,a+mid,a+r+,cmp1);
minv[num][]=maxv[num][]=val[num][]=a[mid].v[];
minv[num][]=maxv[num][]=val[num][]=a[mid].v[];
if(l<=mid-)
{
build(l,mid-,dep+,son[num][]=++size);
update(num,son[num][]);
}
if(mid+<=r)
{
build(mid+,r,dep+,son[num][]=++size);
update(num,son[num][]);
}
}
inline ll s(ll x){return x*x;}
inline ll f(int x)
{
if(x==)return inf;
ll sum=;
for(int i=;i<;++i)
{
if(v[i]<maxv[x][i])sum+=s(maxv[x][i]-v[i]);
if(minv[x][i]<v[i])sum+=s(minv[x][i]-v[i]);
}
return sum;
}
inline ll dis(int x){return s(val[x][]-v[])+s(val[x][]-v[]);}
void ask(int num,int g,ll&ans)
{
if(num==)return;
ll d=dis(num);
if(!vis[M(g,num)]&&ans<d)
{
ans=d;
pos=num;
}
ll lf=f(son[num][]),rf=f(son[num][]);
if(lf>rf)
{
if(lf>ans)ask(son[num][],g,ans);
if(rf>ans)ask(son[num][],g,ans);
}
else
{
if(rf>ans)ask(son[num][],g,ans);
if(lf>ans)ask(son[num][],g,ans);
}
}
int main()
{
// freopen("a.in","r",stdin);
ios::sync_with_stdio(false);
n=read();k=read();
for(int i=;i<=n;++i)a[i].v[]=read(),a[i].v[]=read();
build(,n,,size=);
for(int i=;i<=n;++i)
{
v[]=a[i].v[];
v[]=a[i].v[];
ans=-;
ask(,i,ans);
vis[M(i,pos)]=;
Q.push((pt){i,ans});
}
k=*k;
ll hhh=;
while(k--)
{
pt u=Q.top();
Q.pop();
hhh=u.ans;
v[]=a[u.pos].v[];
v[]=a[u.pos].v[];
ans=-;
ask(,u.pos,ans);
vis[M(u.pos,pos)]=;
Q.push((pt){u.pos,ans});
}
cout<<hhh<<endl;
return ;
}
https://www.luogu.org/problemnew/show/P4357
5.两种操作，一种在平面上添加一个点，一种询问矩形区域内的权值和，允许离线。
离线建树，询问时判断某个点范围内的矩形是否在询问中即可。
#include<bits/stdc++.h>
using namespace std;
const int maxn=2E5+;
const int inf=;
const double d=0.75; int n,m,size,cur,opt;
int son[maxn][],val[maxn][],sum[maxn],sumW[maxn],w[maxn],fa[maxn]; struct rect{int l,r,u,d;}range[maxn];
struct pt{int v[];}a[maxn];
struct query{int a[];}Q[maxn]; bool cmp0(pt x,pt y){return x.v[]<y.v[];}
bool cmp1(pt x,pt y){return x.v[]<y.v[];}
bool in(rect A,rect B){return (B.l<=A.l)&&(A.r<=B.r)&&(A.u<=B.u)&&(B.d<=A.d);}
bool out(rect A,rect B){return (B.r<A.l)||(A.r<B.l)||(B.u<A.d)||(A.u<B.d);}
bool inDot(rect A,int x,int y){return (A.l<=x)&&(x<=A.r)&&(A.d<=y)&&(y<=A.u);} map<pair<int,int>,bool>vis;
map<pair<int,int>,int>where;
pair<int,int> M(int x,int y){return make_pair(x,y);} void build(int l,int r,int dep,int num)
{
int mid=(l+r)>>;
if(dep&)nth_element(a+l,a+mid,a+r+,cmp0);
else nth_element(a+l,a+mid,a+r+,cmp1);
val[num][]=a[mid].v[];
val[num][]=a[mid].v[];
where[M(val[num][],val[num][])]=num;
// cout.width(14*dep-14);
// cout<<val[num][0]<<' '<<val[num][1]<<' '<<range[num].l<<' '<<range[num].r<<' '<<range[num].u<<' '<<range[num].d<<endl;
if(l<=mid-)
{
son[num][]=++size;
if(dep&)range[son[num][]]=(rect){range[num].l,val[num][],range[num].u,range[num].d};
else range[son[num][]]=(rect){range[num].l,range[num].r,val[num][],range[num].d};
fa[size]=num;
build(l,mid-,dep+,size);
}
if(mid+<=r)
{
son[num][]=++size;
if(dep&)range[son[num][]]=(rect){val[num][],range[num].r,range[num].u,range[num].d};
else range[son[num][]]=(rect){range[num].l,range[num].r,range[num].u,val[num][]};
fa[size]=num;
build(mid+,r,dep+,size);
}
}
int ask(rect R,int num)
{
if(num==)return ;
if(in(range[num],R))return sumW[num];
else if(out(range[num],R))return ;
int ans=;
if(inDot(R,val[num][],val[num][]))ans+=w[num];
return ask(R,son[num][])+ask(R,son[num][])+ans;
}
void add(int x,int num)
{
if(num==)return;
sumW[num]+=x;
add(x,fa[num]);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>n;
while(true)
{
cin>>opt;
if(opt==)break;
++m;
if(opt==)
{
++cur;
cin>>a[cur].v[]>>a[cur].v[]>>Q[m].a[];
Q[m].a[]=a[cur].v[];
Q[m].a[]=a[cur].v[];
Q[m].a[]=;
if(vis[M(a[cur].v[],a[cur].v[])])--cur;
vis[M(a[cur].v[],a[cur].v[])]=;
}
else
{
Q[m].a[]=;
cin>>Q[m].a[]>>Q[m].a[]>>Q[m].a[]>>Q[m].a[];
}
}
range[size=]=(rect){,n,n,};
build(,cur,,);
for(int i=;i<=m;++i)
{
if(Q[i].a[]==)
{
add(Q[i].a[],where[M(Q[i].a[],Q[i].a[])]);
w[where[M(Q[i].a[],Q[i].a[])]]+=Q[i].a[];
}
else cout<<ask((rect){Q[i].a[],Q[i].a[],Q[i].a[],Q[i].a[]},)<<endl;
}
return ;
}
https://www.lydsy.com/JudgeOnline/problem.php?id=1176
6.两种操作，一种在矩形区域内点的权值加上给定值，一种询问历史最小值。
多维护个tag和minTag，由于修改是连续的，minTag相当于维护的是最小前缀和。
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int maxn=1E5+;
const int inf=;
int n,m,tot;
int TI,son[maxn][],X[maxn],Y[maxn],fa[maxn];
int minn[maxn][],maxx[maxn][];
ll a[maxn],sum[maxn],val[maxn],valhis[maxn],tag[maxn],taghis[maxn];
map<pair<int,int>,int>where;
struct query
{
int opt,x,y;
}Q[maxn];
struct pt
{
int x,y;
}wait[maxn];
bool cmp1(const pt&A,const pt&B)
{
return A.x<B.x;
}
bool cmp2(const pt&A,const pt&B)
{
return A.y<B.y;
}
inline void hh(int x,int y)
{
if(!y)
return;
minn[x][]=min(minn[x][],minn[y][]);
minn[x][]=min(minn[x][],minn[y][]);
maxx[x][]=max(maxx[x][],maxx[y][]);
maxx[x][]=max(maxx[x][],maxx[y][]);
}
void build(int l,int r,int dep,int&num)
{
if(l>r)
return;
num=++TI;
int mid=(l+r)>>;
if(dep&)
nth_element(wait+l,wait+mid,wait+r+,cmp1);
else
nth_element(wait+l,wait+mid,wait+r+,cmp2);
valhis[num]=val[num]=sum[wait[mid].y]-sum[wait[mid].x-];
X[num]=wait[mid].x,Y[num]=wait[mid].y;
where[make_pair(X[num],Y[num])]=num;
minn[num][]=maxx[num][]=wait[mid].x;
minn[num][]=maxx[num][]=wait[mid].y;
if(dep&)
{
build(l,mid-,dep+,son[num][]);
fa[son[num][]]=num;
build(mid+,r,dep+,son[num][]);
fa[son[num][]]=num;
}
else
{
build(l,mid-,dep+,son[num][]);
fa[son[num][]]=num;
build(mid+,r,dep+,son[num][]);
fa[son[num][]]=num;
}
hh(num,son[num][]);
hh(num,son[num][]);
}
inline void get(int x,int y)
{
valhis[x]=min(valhis[x],val[x]+taghis[y]);
val[x]+=tag[y];
taghis[x]=min(taghis[x],tag[x]+taghis[y]);
tag[x]+=tag[y];
}
inline void pushdown(int num)
{
if(son[num][])
get(son[num][],num);
if(son[num][])
get(son[num][],num);
tag[num]=taghis[num]=;
}
void change(int num,ll x,int p)
{
if(!num||minn[num][]>p||maxx[num][]<p)
return;
if(maxx[num][]<=p&&minn[num][]>=p)
{
tag[num]+=x;
taghis[num]=min(taghis[num],tag[num]);
val[num]+=x;
valhis[num]=min(valhis[num],val[num]);
pushdown(num);
return;
}
if(X[num]<=p&&p<=Y[num])
{
val[num]+=x;
valhis[num]=min(valhis[num],val[num]);
}
pushdown(num);
change(son[num][],x,p);
change(son[num][],x,p);
}
void update(int num)
{
if(!num)
return;
update(fa[num]);
pushdown(num);
}
int main()
{
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=;i<=n;++i)
{
cin>>a[i];
sum[i]=sum[i-]+a[i];
}
map<pair<int,int>,bool>vis;
for(int i=;i<=m;++i)
{
cin>>Q[i].opt>>Q[i].x>>Q[i].y;
if(Q[i].opt==&&!vis[make_pair(Q[i].x,Q[i].y)])
{
wait[++tot]=(pt){Q[i].x,Q[i].y};
vis[make_pair(Q[i].x,Q[i].y)]=;
}
}
int x=;
build(,tot,,x);
for(int i=;i<=m;++i)
{
int opt=Q[i].opt,x=Q[i].x,y=Q[i].y;
if(opt==)
{
ll d=y-a[x];
a[x]=y;
change(,d,x);
}
else
{
update(where[make_pair(x,y)]);
cout<<valhis[where[make_pair(x,y)]]<<endl;
}
}
return ;
}