【bzoj2648&&2716】SJY摆棋子

2015.06.17 14:28 Wed | 17次阅读 | 旧日oi | 固定链接 | 源码

题目大意:一个棋盘上有一些黑点,有两种操作,1.在某个位置加一个黑点,2.查询离某个位置最近的黑点的距离(曼哈顿距离)
题解
kdtree裸题,hzwer照zky的模板写的,我照hzwer的模板写的2333,把一些东西改成我的风格之后他就变成我的模板辣!
之前估价函数那里不是很懂,但是其实就是求左右两边形成的矩形离中间点的最近距离嘛。、
这题还可以cdq分治,但是那个58s卡过,这个16s轻松过~

我的程序

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define N 500005
#define inf 0x3f3f3f3f
#define ls t[x].l
#define rs t[x].r
int n,m,root,D;
struct P
{
    int d[2],mn[2],mx[2],l,r;
    int & operator [](int x) {return d[x];}
    P(int x,int y)
    {
        l=0;r=0;d[0]=x;d[1]=y;
    }
    P(){}
}p[N];
bool operator<(P a,P b)
{
    return a[D]<b[D];
}
inline int dis(P &a,P &b)
{
    return abs(a[0]-b[0])+abs(a[1]-b[1]);
}
struct KDT
{
    int ans;
    P t[N<<1],T;
    void update(int x)
    {
        for(int i=0;i<2;i++)
        {
            if(ls) t[x].mn[i]=min(t[x].mn[i],t[ls].mn[i]),
                    t[x].mx[i]=max(t[x].mx[i],t[ls].mx[i]);
            if(rs) t[x].mn[i]=min(t[x].mn[i],t[rs].mn[i]),
                    t[x].mx[i]=max(t[x].mx[i],t[rs].mx[i]);
        }
    }
    int build(int l,int r,int now)
    {
        D=now;
        int mid=(l+r)>>1;
        nth_element(p+l,p+mid,p+r+1);
        t[mid]=p[mid];
        for(int i=0;i<2;i++) t[mid].mn[i]=t[mid].mx[i]=t[mid][i];
        if(l<mid) t[mid].l=build(l,mid-1,now^1);
        if(mid<r) t[mid].r=build(mid+1,r,now^1);
        update(mid);
        return mid;
    }
    int get(int x,P p)
    {
        int tmp=0;
        for(int i=0;i<2;i++) tmp+=max(0,t[x].mn[i]-p[i]);
        for(int i=0;i<2;i++) tmp+=max(0,p[i]-t[x].mx[i]);
        return tmp;
    }
    void insert(int x,int now)
    {
        if(T[now]>=t[x][now])
        {
            if(rs) insert(rs,now^1);
            else
            {
                rs=++n;t[n]=T;
                for(int i=0;i<2;i++) t[n].mn[i]=t[n].mx[i]=t[n][i];
            }
        }
        else
        {
            if(ls) insert(ls,now^1);
            else
            {
                ls=++n;t[n]=T;
                for(int i=0;i<2;i++) t[n].mn[i]=t[n].mx[i]=t[n][i];
            }
        }
        update(x);  
    }
    void query(int x,int now)
    {
        int d,dl=inf,dr=inf;
        d=dis(t[x],T);
        ans=min(ans,d);
        if(ls) dl=get(ls,T);
        if(rs) dr=get(rs,T);
        if(dl<dr)
        {
            if(dl<ans) query(ls,now^1);
            if(dr<ans) query(rs,now^1);
        }
        else
        {
            if(dr<ans) query(rs,now^1);
            if(dl<ans) query(ls,now^1);
        }
    }
    void ask(int x,int y)
    {
        ans=inf;T=P(x,y);query(root,0);
        printf("%d\n",ans);
    }
    void add(int x,int y)
    {
        T=P(x,y);
        insert(root,0);
    }
}kd;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++) scanf("%d%d",&p[i][0],&p[i][1]);
    root=kd.build(1,n,0);
    int t,x,y;
    while(m--)
    {
        scanf("%d%d%d",&t,&x,&y);
        if(t==1) kd.add(x,y);
        else kd.ask(x,y);
    }
    return 0;
}```