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

    ID: 5026 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>树状数组cdq 分治分治剪枝概率论,统计

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

题目描述

Ayu 在七年前曾经收到过一个天使玩偶,当时她把它当作时间囊埋在了地下。而七年后 的今天,Ayu 却忘了她把天使玩偶埋在了哪里,所以她决定仅凭一点模糊的记忆来寻找它。

我们把 Ayu 生活的小镇看作一个二维平面坐标系,而 Ayu 会不定时地记起可能在某个点 (xmy) 埋下了天使玩偶;或者 Ayu 会询问你,假如她在 (x,y)(x,y),那么她离近的天使玩偶可能埋下的地方有多远。

因为 Ayu 只会沿着平行坐标轴的方向来行动,所以在这个问题里我们定义两个点之间的距离为 dist(A,B)=AxBx+AyBy\operatorname{dist}(A,B)=|A_x-B_x|+|A_y-B_y|。其中 AxA_x 表示点 AA 的横坐标,其余类似。

输入格式

第一行包含两个整数 nnmm,在刚开始时,Ayu 已经知道有 nn 个点可能埋着天使玩偶, 接下来 Ayu 要进行 mm 次操作

接下来 nn 行,每行两个非负整数 (xi,yi)(x_i,y_i),表示初始 nn 个点的坐标。

再接下来 mm 行,每行三个非负整数 t,xi,yit,x_i,y_i

  • 如果 t=1t=1,则表示 Ayu 又回忆起了一个可能埋着玩偶的点 (xi,yi)(x_i,y_i)
  • 如果 t=2t=2,则表示 Ayu 询问如果她在点 (xi,yi)(x_i,y_i),那么在已经回忆出来的点里,离她近的那个点有多远

输出格式

对于每个 t=2t=2 的询问,在单独的一行内输出该询问的结果。

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

提示

数据规模与约定

对于 100%100\% 的数据 保证 1n,m3×1051 \leq n,m\leq 3 \times 10^50xi,yi1060 \leq x_i,y_i \leq 10^6