洛谷 P4169 天使玩偶 / SJY 摆棋子 题解【k-d tree】【估价】

作者: wjyyy 分类: k-d tree,估价,解题报告 发布时间: 2019-06-02 23:49

点击量:39

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;
}

说点什么

avatar
  Subscribe  
提醒
/* */