题目
展开 题目描述 Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。
我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 (xmy) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 (x,y)(x,y)，那么她离近的天使玩偶可能埋下的地方有多远。
因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为 \operatorname{dist}(A,B)=|A_x-B_x|+|A_y-B_y|dist(A,B)=∣A x −B x ∣+∣A y −B y ∣。其中 A_xA x 表示点 AA 的横坐标，其余类似。
输入格式 第一行包含两个整数 nn 和 mm，在刚开始时，Ayu 已经知道有 nn 个点可能埋着天使玩偶， 接下来 Ayu 要进行 mm 次操作
接下来 nn 行，每行两个非负整数 (x_i,y_i)(x i ,y i )，表示初始 nn 个点的坐标。
再接下来 mm 行，每行三个非负整数 t,x_i,y_it,x i ,y i 。
如果 t=1t=1，则表示 Ayu 又回忆起了一个可能埋着玩偶的点 (x_i,y_i)(x i ,y i )。 如果 t=2t=2，则表示 Ayu 询问如果她在点 (x_i,y_i)(x i ,y i )，那么在已经回忆出来的点里，离她近的那个点有多远 输出格式 对于每个 t=2t=2 的询问，在单独的一行内输出该询问的结果。
输入输出样例 输入 #1复制 2 3 1 1 2 3 2 1 2 1 3 3 2 4 2 输出 #1复制 1 2 说明/提示 数据规模与约定 对于 100%100% 的数据 保证 1 \leq n,m\leq 3 \times 10^51≤n,m≤3×10 5 ，0 \leq x_i,y_i \leq 10^60≤x i ,y i ≤10 6 。
思路
kd-tree 这题是要求曼哈顿距离，另外封在结构体里的那个，求的是当前结点，到以该结点为根的子树维护矩形边界的最小曼哈顿距离。
代码
#include<bits/stdc++.h>
#define alpha (0.75)
using namespace std
;
const int N
= 6e5 + 5;
const int INF
= 0x3f3f3f3f;
bool dimension
;
bool reg_dimension
;
int n
,m
,ans
;
struct Point
{
int x
,y
;
Point(int X
= 0,int Y
= 0) :x(X
) ,y(Y
) {}
};
Point a
[N
];
struct Node
*null
;
struct Node
{
int cover
;
Point p
,r1
,r2
;
Node
*son
[2];
void maintain()
{
r1
.x
= min(r1
.x
,min(son
[0]->r1
.x
,son
[1]->r1
.x
)) ;
r1
.y
= min(r1
.y
,min(son
[0]->r1
.y
,son
[1]->r1
.y
)) ;
r2
.x
= max(r2
.x
,max(son
[0]->r2
.x
,son
[1]->r2
.x
)) ;
r2
.y
= max(r2
.y
,max(son
[0]->r2
.y
,son
[1]->r2
.y
)) ;
cover
= son
[0]->cover
+ son
[1]->cover
+ 1;
}
bool is_bad()
{
return max(son
[0]->cover
,son
[1]->cover
) > cover
*alpha
+ 5;
}
int dis(Point p
)
{
if(this == null
) return INF
;
int res
= 0;
if(p
.x
<r1
.x
|| p
.x
>r2
.x
) res
+= p
.x
< r1
.x
? r1
.x
- p
.x
: p
.x
- r2
.x
;
if(p
.y
<r1
.y
|| p
.y
>r2
.y
) res
+= p
.y
< r1
.y
? r1
.y
- p
.y
: p
.y
- r2
.y
;
return res
;
}
};
Node mempool
[N
];
Node
*tail
;
Node
*root
;
bool cmp(Point p1
,Point p2
)
{
if(dimension
== 0) return p1
.x
< p2
.x
|| (p1
.x
== p2
.x
&& p1
.y
< p2
.y
) ;
return p1
.y
< p2
.y
|| (p1
.y
== p2
.y
&& p1
.x
< p2
.x
) ;
}
int Manhattan_dis(Point a
,Point b
)
{
return abs(a
.x
- b
.x
) + abs(a
.y
- b
.y
) ;
}
void init()
{
tail
= mempool
;
null
= tail
++;
null
->son
[0] = null
->son
[1] = null
;
null
->r1
= Point(INF
,INF
) ;
null
->r2
= Point(-INF
,-INF
) ;
null
->cover
= 0;
root
= null
;
}
Node
* new_node(Point key
)
{
Node
*o
;
o
= tail
++;
o
->son
[0] = o
->son
[1] = null
;
o
->cover
= 1;
o
->p
= o
->r1
= o
->r2
= key
;
return o
;
}
void travel(Node
* p
,vector
<Node
*>&x
)
{
if(p
== null
) return;
travel(p
->son
[0],x
) ;
x
.push_back(p
) ;
travel(p
->son
[1],x
) ;
}
Node
* divide(vector
<Node
*>&x
,int l
,int r
,bool d
)
{
if(l
>= r
) return null
;
int mid
= (l
+ r
) >> 1;
dimension
= d
;
Node
*o
= x
[mid
];
o
->son
[0] = divide(x
,l
,mid
,d
^ 1) ;
o
->son
[1] = divide(x
,mid
+ 1,r
,d
^ 1) ;
o
->maintain() ;
return o
;
}
void rebuild(Node
*&o
,bool d
)
{
static vector
<Node
*>v
;
v
.clear() ;
travel(o
,v
) ;
o
= divide(v
,0,v
.size() ,d
) ;
}
Node
* build(int l
,int r
,bool d
)
{
if(l
>= r
) return null
;
int mid
= (l
+ r
) >> 1;
dimension
= d
;
nth_element(a
+ l
,a
+ mid
,a
+ r
,cmp
) ;
Node
*o
= new_node(a
[mid
]) ;
o
->son
[0] = build(l
,mid
,d
^ 1) ;
o
->son
[1] = build(mid
+ 1,r
,d
^ 1) ;
o
->maintain() ;
return o
;
}
Node
** __insert(Node
*&o
,Point key
)
{
if(o
== null
)
{
o
= new_node(key
) ;
reg_dimension
= dimension
;
return &null
;
}
else
{
o
->cover
++;
bool dir
= cmp(key
,o
->p
) ^ 1;
dimension
^= 1;
Node
** res
= __insert(o
->son
[dir
],key
) ;
if(o
->is_bad())
{
res
= &o
;
reg_dimension
= dimension
;
}
o
->maintain() ;
return res
;
}
}
void insert(Point key
)
{
reg_dimension
= dimension
= 0;
Node
** res
= __insert(root
,key
) ;
if(*res
!= null
) rebuild(*res
,reg_dimension
) ;
}
void query(Node
*o
,Point key
)
{
if(o
== null
) return;
ans
= min(ans
,Manhattan_dis(key
,o
->p
)) ;
int dir
= o
->son
[0]->dis(key
) > o
->son
[1]->dis(key
) ;
query(o
->son
[dir
],key
) ;
if(o
->son
[dir
^ 1]->dis(key
) < ans
)
query(o
->son
[dir
^ 1],key
) ;
}
int main()
{
init() ;
n
= read() ; m
= read() ;
for(int i
= 0; i
< n
; i
++) a
[i
].x
= read() ,a
[i
].y
= read() ;
root
= build(0,n
,0) ;
while(m
--)
{
int op
= read() ,x
= read() ,y
= read() ;
if(op
== 1) insert(Point(x
,y
)) ;
else
{
ans
= INF
;
query(root
,Point(x
,y
)) ;
printf("%d\n",ans
) ;
}
}
return 0;
}
