bzoj 2648: SJY摆棋子&&2716: [Violet 3]天使玩偶 --kdtree

2022-11-17 22:32:46

2648: SJY摆棋子&&2716: [Violet 3]天使玩偶

Time Limit: 20 Sec Memory Limit: 128 MB

Description

这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是曼哈顿距离即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。

Input

第一行两个数 N M

以后M行，每行3个数 t x y

如果t=1 那么放下一个黑色棋子

如果t=2 那么放下一个白色棋子

Output

对于每个T=2 输出一个最小距离

Sample Input

2 3
1 1
2 3
2 1 2
1 3 3
2 4 2

Sample Output

1
2

HINT

kdtree可以过

Source

照着zgz233打了一遍板子qaq

#include<map>

#include<cmath>

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

#define inf 1000000007

#define ll long long

#define N 1000010

inline int rd()

{

    int x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

struct qaz

{

    int d[],mn[],mx[],l,r;

    int& operator[](int x){return d[x];}

}p[N],tr[N],T;

int D;

bool operator <(qaz a,qaz b){return a[D]<b[D];}

int rt;

#define ls tr[x].l

#define rs tr[x].r

inline void upd(int x)

{

    for(int i=;i<;i++)

    {

        if(ls) tr[x].mn[i]=min(tr[x].mn[i],tr[ls].mn[i]),tr[x].mx[i]=max(tr[x].mx[i],tr[ls].mx[i]);

        if(rs) tr[x].mn[i]=min(tr[x].mn[i],tr[rs].mn[i]),tr[x].mx[i]=max(tr[x].mx[i],tr[rs].mx[i]);

    }

}

int build(int l,int r,int t)

{

    D=t;

    int mid=l+r>>;

    nth_element(p+l,p+mid,p+r+);

    tr[mid]=p[mid];

    for(int i=;i<;i++) tr[mid].mn[i]=tr[mid].mx[i]=tr[mid][i];

    if(l<mid) tr[mid].l=build(l,mid-,t^);

    if(mid<r) tr[mid].r=build(mid+,r,t^);

    upd(mid);return mid;

}

int n,m;

void ins(int x,int t)

{

    if(T[t]<tr[x][t])

    {

        if(ls) ins(ls,t^);

        else{ls=++n,tr[n]=T;}

    }

    else

    {

        if(rs) ins(rs,t^);

        else{rs=++n,tr[n]=T;}

    }

    upd(x);

}

int ans;

int dis(qaz a,qaz b){return abs(a[]-b[])+abs(a[]-b[]);}

int gtdis(qaz a,qaz b)

{

    int ji=;

    for(int i=;i<;i++)

        ji+=max(,b.mn[i]-a[i])+max(,a[i]-b.mx[i]);

    return ji;

}

void fd(int x,int t)

{

    int d=dis(tr[x],T),dl=inf,dr=inf;

    ans=min(d,ans);

    if(ls) dl=gtdis(T,tr[ls]);

    if(rs) dr=gtdis(T,tr[rs]);

    if(dl<dr)

    {

        if(dl<ans) fd(ls,t^);

        if(dr<ans) fd(rs,t^);

    }

    else

    {

        if(dr<ans) fd(rs,t^);

        if(dl<ans) fd(ls,t^);

    }

}

int main()

{

    n=rd();m=rd();

    for(int i=;i<=n;i++) p[i][]=rd(),p[i][]=rd();

    rt=build(,n,);

    int op,x,y;

    while(m--)

    {

        T.l=T.r=;op=rd();

        T.mn[]=T.mx[]=T[]=rd();

        T.mn[]=T.mx[]=T[]=rd();

        if(op==) ins(rt,);

        else

        {

            ans=inf;

            fd(rt,);

            printf("%d\n",ans);

        }

    }

    return ;

}

码农公寓