SJY摆棋子

Time Limit: 20 Sec Memory Limit: 128 MB

Description

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

Input

第一行两个数 N M

然后N行，每行2个数 x y，表示初始棋子

以后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

N<=500000 , M<=500000

Main idea

在平面上加入黑点，对于询问一个坐标到其它点的曼哈顿距离中最小的一个。

Solution

这题显然是一道KD-tree的模板题。

我们来考虑如何估价，由于求的是最小的曼哈顿距离，我们可以这样估价：

img

（其实我也并不懂为什么可以这样估，详情可以查询**“n+e KDtree在信息学奥赛中的应用”**）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<bits/stdc++.h>
using namespace std;

const int ONE=1000005;
const int INF=2147483640;

int n,m;
int t,x,y;
int cnt,Ans;
int root;
int Ran;

struct power
{
    int l,r;
    int x,y;
    int minx,miny;
    int maxx,maxy;
}a[ONE];

int get()
{
    int res=1,Q=1;char c;
    while( (c=getchar())<48 || c>57 )
        if(c=='-')Q=-1;
    res=c-48;
    while( (c=getchar())>=48 && c<=57 )
        res=res*10+c-48;
    return res*Q;
}

namespace KD
{
    void Update(int i)
    {
        if(a[i].l)
        {
            a[i].minx=min(a[i].minx,a[a[i].l].minx);    a[i].miny=min(a[i].miny,a[a[i].l].miny);
            a[i].maxx=max(a[i].maxx,a[a[i].l].maxx);    a[i].maxy=max(a[i].maxy,a[a[i].l].maxy);
        }
        if(a[i].r)
        {
            a[i].minx=min(a[i].minx,a[a[i].r].minx);    a[i].miny=min(a[i].miny,a[a[i].r].miny);
            a[i].maxx=max(a[i].maxx,a[a[i].r].maxx);    a[i].maxy=max(a[i].maxy,a[a[i].r].maxy);
        }
    }

    int cmp(const power &a,const power &b)
    {
        if(Ran) return a.x<b.x;
        return a.y<b.y;
    }

    int Build(int l,int r,int T)
    {
        int mid=(l+r)/2;
        Ran=T;
        nth_element(a+l, a+mid+1, a+r+1, cmp);
        if(l<mid) a[mid].l = Build(l,mid-1,T^1);
        if(mid<r) a[mid].r = Build(mid+1,r,T^1);
        Update(mid);
        return mid;
    }
}

void Update(int &i,int x,int y,int T)
{
    if(!i)
    {
        i=++cnt;
        a[i].x=a[i].minx=a[i].maxx=x;
        a[i].y=a[i].miny=a[i].maxy=y;
        return;
    }

    if(T)
    {
        if(x < a[i].x) Update(a[i].l,x,y,T^1);
        else Update(a[i].r,x,y,T^1);
        KD::Update(i);
    }
    else
    {
        if(y < a[i].y) Update(a[i].l,x,y,T^1);
        else Update(a[i].r,x,y,T^1);
        KD::Update(i);
    }
}

int dist(int x1,int y1,int x2,int y2)
{
    return abs(x1-x2)+abs(y1-y2);
}

int dist(int i,int x,int y)
{
    return max(a[i].minx-x,0)+max(x-a[i].maxx,0) + max(a[i].miny-y,0)+max(y-a[i].maxy,0);
}

void Query(int i,int x,int y)
{
    if(!i) return;
    Ans=min(Ans,dist(x,y , a[i].x,a[i].y));
    int l=dist(a[i].l,x,y);
    int r=dist(a[i].r,x,y);
    if(l<r)
    {
        if(l<=Ans) Query(a[i].l,x,y);
        if(r<=Ans) Query(a[i].r,x,y);
    }
    else
    {
        if(r<=Ans) Query(a[i].r,x,y);
        if(l<=Ans) Query(a[i].l,x,y);
    }
}

int main()
{
    n=get();    m=get();
    for(int i=1;i<=n;i++)
    {
        x=get();    y=get();
        a[i].x=a[i].minx=a[i].maxx=x;
        a[i].y=a[i].miny=a[i].maxy=y;
    }

    cnt=n;
    root=KD::Build(1,n,1);

    for(int i=1;i<=m;i++)
    {
        t=get();    x=get();    y=get();
        if(t==1)
        {
            n++;
            a[n].x=a[n].minx=a[n].maxx=x;
            a[n].y=a[n].miny=a[n].maxy=y;
            Update(root,x,y,1);
        }
        else
        {
            Ans=INF;
            Query(root,x,y);
            printf("%d\n",Ans);
        }
    }
}