TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2739
  • 問題
  • P2739【Violet III】天使玩偶
    制限 : 時間制限 : 200000 MS   メモリ制限 : 524288 KB
    審判説明 : 10s
    問題説明

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

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

    因为Ayu只会沿着平行坐标轴的方向来行动,所以在这个问题里我们定义两个点之间的距离为 \(dist(A,B)=|Ax-Bx|+|Ay-By|\) 。其中 \(Ax\) 表示点A的横坐标,其余类似。

    入力形式

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

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

    再接下来 \(m\) 行,每行三个非负整数 \(t,x_i,y_i\)
    如果 \(t=1\) ,则表示Ayu又回忆起了一个可能埋着玩偶的点 \((x_i,y_i)\)
    如果 \(t=2\) ,则表示Ayu询问如果她在点 \((x_i,y_i)\) ,那么在已经回忆出来的点里,离她最 近的那个点有多远。

    出力形式

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

    サンプル入力

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

    サンプル出力

    1
    2

    ヒント

    对于100%的数据\(n,m\leq 5\times10^5\)

    编号 \(\qquad\) \(n,m\leq\) \(\qquad\) \(x_i,y_i\leq\) \(\qquad\) \(t\in\)
    1 100 100 {1,2}
    2 500 5,000 {1,2}
    3 1,000 100,000 {1,2}
    4 1,000 100,000 {1,2}
    5 30,000 1,000 {1,2}
    6 50,000 1,500 {1,2}
    7 100,000 2,000 {1,2}
    8 100,000 2,000 {1,2}
    9 250,000 250,000 {1,2}
    10 500,000 500,000 {1,2}
    11 80,000 80,000 {2}
    12 100,000 100,000 {2}
    13 200,000 200,000 {2}
    14 500,000 500,000 {2}
    15 100,000 100,000 {1,2}
    16 150,000 150,000 {1,2}
    17 300,000 300,000 {1,2}
    18 500,000 500,000 {1,2}
    19 300,000 1,000,000 {1,2}
    20 300,000 1,000,000 {1,2}