2019.01.14 bzoj2648: SJY摆棋子（kd-tree）

传送门

kd−treekd-treekd−tree模板题。

题意简述：支持在平面上插入一个点，求对于一个点的最近点对。

思路：cdqcdqcdq是一种很不错的分治方法只是好像码量有点窒息

所以我用了kd−treekd-treekd−tree来做。

其实就是两个维度分别作为键值来建立二叉搜索树即可。

这道题在查询时可以通过判断下一层的有没有可能对答案有贡献来剪个枝。

由于蒟蒻暂时没写过方差划分因此时间很慢。

代码：

#include<bits/stdc++.h>
#define mid (l+r>>1)
#define ri register int
using namespace std;
inline int read(){
    int ans=0;
    char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
    return ans;
}
typedef pair<int,int> pii;
const int N=1e6+5,inf=0x3f3f3f3f;
int n,m,mx[N][2],mn[N][2],son[N][2],ans,tot=0;
bool cmpdir;
struct Pot{
    int a[2];
    inline int&operator[](const int&k){return a[k];}
    inline const int&operator[](const int&k)const{return a[k];}
}p[N];
inline bool cmp(const Pot&a,const Pot&b){return a[cmpdir]<b[cmpdir];}
inline void pushup(int p){
    if(son[p][0]){
        mn[p][0]=min(mn[p][0],mn[son[p][0]][0]);
        mx[p][0]=max(mx[p][0],mx[son[p][0]][0]);
        mn[p][1]=min(mn[p][1],mn[son[p][0]][1]);
        mx[p][1]=max(mx[p][1],mx[son[p][0]][1]);
    }
    if(son[p][1]){
        mn[p][0]=min(mn[p][0],mn[son[p][1]][0]);
        mx[p][0]=max(mx[p][0],mx[son[p][1]][0]);
        mn[p][1]=min(mn[p][1],mn[son[p][1]][1]);
        mx[p][1]=max(mx[p][1],mx[son[p][1]][1]);
    }
}
inline int build(int l,int r,bool d){
    cmpdir=d;
    nth_element(p+l,p+mid,p+r+1,cmp);
    mn[mid][0]=mx[mid][0]=p[mid][0],mn[mid][1]=mx[mid][1]=p[mid][1];
    if(l<mid)son[mid][0]=build(l,mid-1,d^1);
    if(r>mid)son[mid][1]=build(mid+1,r,d^1);
    return pushup(mid),mid;
}
inline void insert(int k,Pot v,bool d){
    if(p[k][d]<=v[d]){
        if(son[k][1])insert(son[k][1],v,d^1);
        else{
            p[son[k][1]=++tot]=v;
            mx[tot][0]=mn[tot][0]=v[0];
            mx[tot][1]=mn[tot][1]=v[1];
        }
    }
    else{
        if(son[k][0])insert(son[k][0],v,d^1);
        else{
            p[son[k][0]=++tot]=v;
            mx[tot][0]=mn[tot][0]=v[0];
            mx[tot][1]=mn[tot][1]=v[1];
        }
    }
    pushup(k);
}
inline int ask(int k,Pot v){
    int ret=0;
    ret+=max(0,mn[k][0]-v[0]);
    ret+=max(0,mn[k][1]-v[1]);
    ret+=max(0,v[0]-mx[k][0]);
    ret+=max(0,v[1]-mx[k][1]);
    return ret;
}
inline int dist(Pot a,Pot b){return abs(a[0]-b[0])+abs(a[1]-b[1]);}
inline void query(int k,Pot v,bool d){
    ans=min(ans,dist(p[k],v));
    int al=inf,ar=inf;
    if(son[k][0])al=ask(son[k][0],v);
    if(son[k][1])ar=ask(son[k][1],v);
    if(al<ar){
        if(al<ans)query(son[k][0],v,d^1);
        if(ar<ans)query(son[k][1],v,d^1);
    }
    else{
        if(ar<ans)query(son[k][1],v,d^1);
        if(al<ans)query(son[k][0],v,d^1);
    }
}
int main(){
    n=read(),m=read(),tot=0;
    for(ri i=1,x,y;i<=n;++i)x=read(),y=read(),p[++tot]=(Pot){x,y};
    for(ri rt=build(1,n,0),i=1,x,y,op;i<=m;++i){
        op=read(),x=read(),y=read();
        if(op==1)insert(rt,(Pot){x,y},0);
        else ans=inf,query(rt,(Pot){x,y},0),cout<<ans<<'\n';
    }
    return 0;
}

巴特西

2019.01.14 bzoj2648: SJY摆棋子（kd-tree）

最新文章

热门文章