P4169 [Violet]天使玩偶/SJY摆棋子

链接

luogu

思路

luogu以前用CDQ一直过不去。
bzoj还是卡时过去的。
今天终于用k-dtree给过了。

代码

#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f,N=1e6+7;;
const double alph(0.75);
int WD,ans,rub[N],tot,top;
struct Point {
    int x[2];
    bool operator < (const Point b) const {
        return x[WD]<b.x[WD];
    }
}p[N];
struct node {
    int mi[2],ma[2],ls,rs,siz;
    Point tp;
}e[N];
int newnode() {
    if(top) return rub[top--];
    return ++tot;
}
void up(int u) {
    for(int i=0;i<2;++i) {
        e[u].mi[i]=e[u].ma[i]=e[u].tp.x[i];
        if(e[u].ls) {
            e[u].mi[i]=min(e[u].mi[i],e[e[u].ls].mi[i]);
            e[u].ma[i]=max(e[u].ma[i],e[e[u].ls].ma[i]);    
        }
        if(e[u].rs) {
            e[u].mi[i]=min(e[u].mi[i],e[e[u].rs].mi[i]);
            e[u].ma[i]=max(e[u].ma[i],e[e[u].rs].ma[i]);
        }
    }
    e[u].siz=e[e[u].ls].siz+e[e[u].rs].siz+1;
}
int build(int l,int r,int wd) {
    if(l>r) return 0;
    int u=newnode(),mid=(l+r)>>1;
    WD=wd;
    nth_element(p+l,p+mid,p+r+1);
    e[u].tp=p[mid];
    e[u].ls=build(l,mid-1,wd^1);
    e[u].rs=build(mid+1,r,wd^1);
    up(u);
    return u;
}
void pia(int u,int num) {
    if(e[u].ls) pia(e[u].ls,num);
    p[num+e[e[u].ls].siz+1]=e[u].tp;
    rub[++top]=u;
    if(e[u].rs) pia(e[u].rs,num+e[e[u].ls].siz+1);
}
void check(int &u,int wd) {
    if(alph*e[u].siz<e[e[u].ls].siz||alph*e[u].siz<e[e[u].rs].siz)
        pia(u,0),u=build(1,e[u].siz,wd);
}
void insert(Point tmp,int &u,int wd) {
    if(!u) {u=newnode(),e[u].tp=tmp;e[u].ls=e[u].rs=0;up(u);return;}
    if(e[u].tp.x[wd]<tmp.x[wd]) insert(tmp,e[u].rs,wd^1);
    else insert(tmp,e[u].ls,wd^1);
    up(u),check(u,wd);
}
int getdis(Point tmp,int u) {
    int res=0;
    for(int i=0;i<=1;++i)
        res+=max(0,e[u].mi[i]-tmp.x[i])+max(0,tmp.x[i]-e[u].ma[i]);
    return res;
}
int dis(Point a,Point b) {
    return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);
}
void query(Point tmp,int u) {
    ans=min(ans,dis(e[u].tp,tmp));
    int dl=INF,dr=INF;
    if(e[u].ls) dl=getdis(tmp,e[u].ls);
    if(e[u].rs) dr=getdis(tmp,e[u].rs);
    if(dl<dr) {
        if(dl<ans) query(tmp,e[u].ls);
        if(dr<ans) query(tmp,e[u].rs);
    } else {
        if(dr<ans) query(tmp,e[u].rs);
        if(dl<ans) query(tmp,e[u].ls);
    }
}
int main() {
    int opt,n,m,rt;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) scanf("%d%d",&p[i].x[0],&p[i].x[1]);
    rt=build(1,n,0);
    while(m--) {
        Point tmp;
        scanf("%d%d%d",&opt,&tmp.x[0],&tmp.x[1]);
        if(opt==1) insert(tmp,rt,0);
        else ans=INF,query(tmp,rt),printf("%d\n",ans);
    }
    return 0;
}