看了青岛赛区的题简单学了一下kd，感觉这东西还是挺厉害的
一般kd树找最近点对最坏是O(n)，但是随机情况下跑得还是很快的
kd树是一棵BST，但是每一层的关键字不同
一般写法是按照每一维轮流来，这一维小的放左子树，大的放右边的
每个节点再维护这节点所管辖的节点每一维的范围，这样基本就能做题了
kdtree一般是静态直接建好的，插入可以套一个替罪羊树重构做到logn，但是据说慢
那么怎么查询最近点呢
每到一个节点，比较通过这节点所管辖点的每一维的范围，估计出可能最小的距离
优先访问估值优的子树
可以看到查询几乎就是个搜索+剪枝，所以最坏是O(n)，最远点类似
这样bzoj1941就解了
#include<bits/stdc++.h> using namespace std;
const int inf=1e9+;
int key,dmx,dmi,root,n,x[],y[]; struct node
{
int son[],mi[],mx[],d[];
friend bool operator <(node a,node b)
{
return a.d[key]<b.d[key];
}
friend int dis(node a,node b)
{
return abs(a.d[]-b.d[])+abs(a.d[]-b.d[]);
}
} po; struct kdtree
{
node a[];
void init()
{
a[].son[]=a[].son[]=;
for (int i=; i<; i++)
{
a[].mi[i]=inf;
a[].mx[i]=-inf;
}
}
void update(int x)
{
int l=a[x].son[],r=a[x].son[];
for (int i=; i<; i++)
{
a[x].mi[i]=min(a[x].d[i],min(a[l].mi[i],a[r].mi[i]));
a[x].mx[i]=max(a[x].d[i],max(a[l].mx[i],a[r].mx[i]));
}
}
int build(int l,int r,int cur)
{
if (l>r) return ;
int m=(l+r)>>;
key=cur; nth_element(a+l,a+m,a+r+);
a[m].son[]=build(l,m-,cur^);
a[m].son[]=build(m+,r,cur^);
update(m);
return m;
}
int getmi(int x)
{
int s=;
for (int i=;i<;i++)
s+=max(po.d[i]-a[x].mx[i],)+max(a[x].mi[i]-po.d[i],);
return s;
}
int getmx(int x)
{
int s=;
for (int i=;i<;i++)
s+=max(abs(po.d[i]-a[x].mi[i]),abs(po.d[i]-a[x].mx[i]));
return s;
}
void askmx(int q)
{
dmx=max(dmx,dis(a[q],po));
int l=a[q].son[],r=a[q].son[],dl=-inf,dr=-inf;
if (l) dl=getmx(l);
if (r) dr=getmx(r);
if (dl>dr)
{
if (dl>dmx) askmx(l);
if (dr>dmx) askmx(r);
}
else {
if (dr>dmx) askmx(r);
if (dl>dmx) askmx(l);
}
}
void askmi(int q)
{
int dd=dis(a[q],po); if (dd) dmi=min(dmi,dd);
int l=a[q].son[],r=a[q].son[],dl=inf,dr=inf;
if (l) dl=getmi(l);
if (r) dr=getmi(r);
if (dl<dr)
{
if (dl<dmi) askmi(l);
if (dr<dmi) askmi(r);
}
else {
if (dr<dmi) askmi(r);
if (dl<dmi) askmi(l);
}
}
} kd; int main()
{
kd.init();
scanf("%d",&n);
for (int i=; i<=n; i++)
{
scanf("%d%d",&x[i],&y[i]);
kd.a[i].d[]=x[i];
kd.a[i].d[]=y[i];
}
root=kd.build(,n,); int ans=inf;
for (int i=;i<=n;i++)
{
dmx=-inf,dmi=inf;
po.d[]=x[i],po.d[]=y[i];
kd.askmx(root); kd.askmi(root);
ans=min(ans,dmx-dmi);
}
printf("%d\n",ans);
}
bzoj1941
hdu5992要加一维价格剪枝，如果这个节点所辖节点的最小价格都比询问大就不访问了
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
const int inf=1e9+;
int key,root,n,m;
ll len;
ll sqr(ll x)
{
return x*x;
} struct node
{
int d[],mi[],mx[],son[],id;
friend bool operator <(node a,node b)
{
return a.d[key]<b.d[key];
}
friend ll dis(node a,node b)
{
return sqr(a.d[]-b.d[])+sqr(a.d[]-b.d[]);
}
} po,ans; struct kdtree
{
node a[];
void init()
{
a[].son[]=a[].son[]=;
for (int i=; i<; i++)
{
a[].mi[i]=inf;
a[].mx[i]=-inf;
}
}
void update(int x)
{
int l=a[x].son[],r=a[x].son[];
for (int i=; i<; i++)
{
a[x].mi[i]=min(a[x].d[i],min(a[l].mi[i],a[r].mi[i]));
a[x].mx[i]=max(a[x].d[i],max(a[l].mx[i],a[r].mx[i]));
}
}
int build(int l,int r,int cur)
{
if (l>r) return ;
int m=(l+r)>>;
key=cur; nth_element(a+l,a+m,a+r+);
a[m].son[]=build(l,m-,cur^);
a[m].son[]=build(m+,r,cur^);
update(m);
return m;
}
void check(int q)
{
if (a[q].d[]>po.d[]) return;
ll l=dis(a[q],po);
if ((len>l)||((len==l)&&ans.id>a[q].id))
{
ans=a[q];
len=l;
}
}
ll get(int q)
{
if (!q||a[q].mi[]>po.d[]) return 1e18+;
ll s=;
for (int i=; i<; i++)
{
if (po.d[i]<a[q].mi[i]) s+=sqr(po.d[i]-a[q].mi[i]);
if (po.d[i]>a[q].mx[i]) s+=sqr(po.d[i]-a[q].mx[i]);
}
return s;
}
void ask(int q)
{
if (a[q].mi[]>po.d[]) return;
check(q);
int l=a[q].son[],r=a[q].son[];
ll dl=get(l),dr=get(r);
if (dl<dr)
{
if (dl<=len) ask(l);
if (dr<=len) ask(r);
}
else {
if (dr<=len) ask(r);
if (dl<=len) ask(l);
}
}
} kd; int main()
{
kd.init();
int cas;
scanf("%d",&cas);
while (cas--)
{
scanf("%d%d",&n,&m);
for (int i=; i<=n; i++)
{
int x,y,c;
scanf("%d%d%d",&x,&y,&c);
kd.a[i].d[]=x; kd.a[i].d[]=y; kd.a[i].d[]=c;
kd.a[i].id=i;
}
root=kd.build(,n,);
for (int i=; i<=m; i++)
{
scanf("%d%d%d",&po.d[],&po.d[],&po.d[]);
len=1e18; kd.ask(root);
printf("%d %d %d\n",ans.d[],ans.d[],ans.d[]);
}
}
}
hdu5992