题解 BZOJ 2648 SJY摆棋子

双倍经验2716.
KD-Tree模板题。
注意一下”nth_element()”
参考: http://blog.csdn.net/jiangshibiao/article/details/34144829

code:

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,D,root,x,y;
struct N{
    int d[2];
    int l,r;
    int min[2];
    int max[2];
}a[1000005];
bool cmp(const N&a,const N&b){
    if(a.d[D]!=b.d[D]) return a.d[D]<b.d[D];
    return a.d[D^1]<b.d[D^1];
}
inline void up(int k,int s){
    a[k].min[0]=min(a[k].min[0],a[s].min[0]);
    a[k].min[1]=min(a[k].min[1],a[s].min[1]);
    a[k].max[0]=max(a[k].max[0],a[s].max[0]);
    a[k].max[1]=max(a[k].max[1],a[s].max[1]);
}
int bd(int l,int r,int d){
    D=d;
    int mid=(l+r)>>1;
    nth_element(a+l,a+mid+1,a+r+1,cmp);
    a[mid].min[0]=a[mid].max[0]=a[mid].d[0];
    a[mid].min[1]=a[mid].max[1]=a[mid].d[1];
    if(l!=mid) a[mid].l=bd(l,mid-1,d^1);
    if(r!=mid) a[mid].r=bd(mid+1,r,d^1);
    if(a[mid].l) up(mid,a[mid].l);
    if(a[mid].r) up(mid,a[mid].r);
    return mid;
}
const int inf=0x7fffffff;
int ans;
int getdis(int k){
    int ret=0;
    if(x<a[k].min[0]) ret+=a[k].min[0]-x;
    if(x>a[k].max[0]) ret+=x-a[k].max[0];
    if(y<a[k].min[1]) ret+=a[k].min[1]-y;
    if(y>a[k].max[1]) ret+=y-a[k].max[1];
    return ret;
}
void ask(int k){
    int d0=abs(a[k].d[0]-x)+abs(a[k].d[1]-y);
    if(d0<ans) ans=d0;
    int d1=(a[k].l)?getdis(a[k].l):inf;
    int d2=(a[k].r)?getdis(a[k].r):inf;
    if(d1<d2){
        if(d1<ans) ask(a[k].l);
        if(d2<ans) ask(a[k].r);
    }else{
        if(d2<ans) ask(a[k].r);
        if(d1<ans) ask(a[k].l);
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&a[i].d[0],&a[i].d[1]);
    }
    root=bd(1,n,0);
    for(int i=0,t;i<m;i++){
        scanf("%d%d%d",&t,&x,&y);
        if(t==1){
            n++;
            a[n].min[0]=a[n].max[0]=a[n].d[0]=x;
            a[n].min[1]=a[n].max[1]=a[n].d[1]=y;
            int p=root,D=0;
            while(1){
                up(p,n);
                if(a[n].d[D]<a[p].d[D]){
                    if(!a[p].l) {
                        a[p].l=n;
                        break;
                    }else{
                        p=a[p].l;
                    }
                }else{
                    if(!a[p].r) {
                        a[p].r=n;
                        break;
                    }else{
                        p=a[p].r;
                    }
                }
                D^=1;
            }
        }else{
            ans=inf;
            ask(root);
            printf("%d\n",ans);
        }
    }
    return 0;
}
评论小助手

评论正在加载...

Tip: 点击下方链接切换到 Disqus 评论框可以获得邮件提醒哦
🗣️ 加载 Disqus 评论框