洛谷 P4169 天使玩偶 / SJY 摆棋子 题解【k-d tree】【估价】
点击量：234
k-d tree 貌似总是会被卡掉一两个点…不过 OI 赛制还是很好的
题目描述
Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。
我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 $(x,y)$ 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 $(x,y)$，那么她离近的天使玩偶可能埋下的地方有多远。
因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为 $dist(A,B)=|Ax-Bx|+|Ay-By|$。其中 $Ax$ 表示点 $A$ 的横坐标，其余类似。
输入输出格式
输入格式：
第一行包含两个整数 $n$ 和 $m$，在刚开始时，Ayu 已经知道有 $n$ 个点可能埋着天使玩偶， 接下来 Ayu 要进行 $m$ 次操作。
接下来 $n$ 行，每行两个非负整数 $(x_i,y_i)$，表示初始 $n$ 个点的坐标。
再接下来 $m$ 行，每行三个非负整数 $t,x_i,y_i$。
如果 $t=1$，则表示 Ayu 又回忆起了一个可能埋着玩偶的点 $(x_i,y_i)$。
如果 $t=2$，则表示 Ayu 询问如果她在点 $(x_i,y_i)$，那么在已经回忆出来的点里，离她近的那个点有多远。
输出格式：
对于每个 $t=2$ 的询问，在单独的一行内输出该询问的结果。
输入输出样例
输入样例#1：
2 3 1 1 2 3 2 1 2 1 3 3 2 4 2输出样例#1：
1 2说明
$n,m\le300000$
$x_i,y_i\le1000000$
题解：
这个题可以用作 cdq 分治入门，但是 k-d tree 在思维难度上会小很多。
可以认为，本题的插入操作是直接在 k-d tree 中插入节点，查询操作可以在 k-d tree 上进行。
分析 k-d tree 可以维护的信息。一个节点会维护子树所构成的边与坐标轴平行的矩形，并不能代表子树内任意一个节点来对答案产生贡献。此时我们可以考虑暴力遍历子树，考虑复杂度，当然不能全部遍历。
在一些搜索中，我们可以用最优性剪枝。也就是说，如果当前搜索的结果的最优可能值还没有已知最优值优，那么就不继续搜了。
在 k-d tree 上也是如此。假设我们即将要进入一棵子树遍历，这棵子树的左右边界分别为 $lx,rx$，上下边界分别为 $ry,ly$。那么 $(x,y)$ 到这个矩形的最小距离一定是到这个矩形边界的最小距离，即 $dis_{\min}=\max(|lx-x|,|rx-x|)+\max(|ly-y|,|ry-y|)$。
考虑到 $(x,y)$ 在矩形内的情况，此时距离为 $0$，把上述式子改写为 $dis_{\min}=\max(\max(lx-x,0),\max(rx-x,0))+\max(\max(ly-y,0),\max(ry-y,0))$ 就能解决这个问题。
可以认为它是个估价函数。对于两棵子树，可以先进入估价优，即这个函数的值较小的子树搜索；如果函数值大于之前搜过的最优值，那么可以直接返回了。
这样的话，复杂度在最坏情况下也只有 $O(\sqrt n)$，均摊是 $O(\log n)$ 的。
这次感觉小数组放在后面常数会小一些不知道为什么。k-d tree 的调参也是件麻烦的事情。
总时间复杂度 $O(n\log n)$。
Code：
// luogu-judger-enable-o2
#pragma GCC optimize("-Ofast")
#include<cstdio>
#include<cstring>
#include<algorithm>
#define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[2100000],*p1=buf,*p2=buf;
int read()
{
int x=0;
char ch=gc();
while(ch<'0'||ch>'9')
ch=gc();
while(ch>='0'&&ch<='9')
{
x=x*10+(ch&15);
ch=gc();
}
return x;
}
int Max(int x,int y){return x>y?x:y;}
int Min(int x,int y){return x<y?x:y;}
int Abs(int x){return x<0?-x:x;}
int ch[1000100][2],c[1000100][2],x[1000100][2],y[1000100][2],sz[1000100],pcnt=0;
int Newnode(int X,int Y)
{
++pcnt;
c[pcnt][0]=x[pcnt][0]=x[pcnt][1]=X;
c[pcnt][1]=y[pcnt][0]=y[pcnt][1]=Y;
sz[pcnt]=1;
return pcnt;
}
#define ls ch[rt][0]
#define rs ch[rt][1]
void maintain(int rt)
{
sz[rt]=sz[ls]+1+sz[rs];
x[rt][0]=Min(c[rt][0],Min(x[ls][0],x[rs][0]));
x[rt][1]=Max(c[rt][0],Max(x[ls][1],x[rs][1]));
y[rt][0]=Min(c[rt][1],Min(y[ls][0],y[rs][0]));
y[rt][1]=Max(c[rt][1],Max(y[ls][1],y[rs][1]));
}
int a[1000100],cnt=0;
bool cmp0(int x_,int y_)
{return c[x_][0]==c[y_][0]?c[x_][1]<c[y_][1]:c[x_][0]<c[y_][0];}
bool cmp1(int x_,int y_)
{return c[x_][1]==c[y_][1]?c[x_][0]<c[y_][0]:c[x_][1]<c[y_][1];}
void build(int &rt,int l,int r,int d)
{
if(l>r)
{
rt=0;
return;
}
int mid=(l+r)>>1;
std::nth_element(a+l,a+mid,a+r+1,d?cmp1:cmp0);
rt=a[mid];
build(ls,l,mid-1,!d);
build(rs,mid+1,r,!d);
maintain(rt);
}
void Insert(int &rt,int nd,int d)
{
if(!rt)
{
rt=nd;
return;
}
Insert(ch[rt][c[nd][d]>=c[rt][d]],nd,!d);
maintain(rt);
}
void dfs(int rt)
{
if(ls)
dfs(ls);
a[++cnt]=rt;
if(rs)
dfs(rs);
}
void Find(int &rt,int nd,int d)
{
if(rt==nd)
return;
if(Max(sz[ls],sz[rs])>sz[rt]*.68)
{
cnt=0;
dfs(rt);
build(rt,1,cnt,d);
return;
}
Find(ch[rt][c[nd][d]>=c[rt][d]],nd,!d);
}
int ans=0;
int dis(int X,int Y,int t)//t is a node
{
if(!t)
return 0x7fffffff;
return Max(Max(x[t][0]-X,0),Max(X-x[t][1],0))+Max(Max(y[t][0]-Y,0),Max(Y-y[t][1],0));
}
void ask(int rt,int X,int Y)
{
ans=Min(ans,Abs(c[rt][0]-X)+Abs(c[rt][1]-Y));
int d1=dis(X,Y,ls),d2=dis(X,Y,rs);
if(d1<d2)
{
if(d1<ans)
ask(ls,X,Y);
if(d2<ans)
ask(rs,X,Y);
}
else
{
if(d2<ans)
ask(rs,X,Y);
if(d1<ans)
ask(ls,X,Y);
}
}
int root;
int main()
{
#ifdef wjyyy
freopen("16.in","r",stdin);
#endif
x[0][0]=y[0][0]=0x7fffffff;
int n=read();
int m=read(),op,u,v;
for(int i=1;i<=n;++i)
{
u=read();
v=read();
Insert(root,Newnode(u,v),0);
Find(root,pcnt,0);
}
for(int i=1;i<=m;++i)
{
op=read();
u=read();
v=read();
if(op==1)
{
Insert(root,Newnode(u,v),0);
Find(root,pcnt,0);
}
else
{
ans=0x7fffffff;
ask(root,u,v);
printf("%d\n",ans);
}
}
return 0;
}
说点什么