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

    • 875通过
    • 5.9K提交
  • 题目提供者 kkksc03 吉祥物
  • 评测方式 云端评测
  • 标签 cdq分治 分治 剪枝 树状数组 概率论,统计 高性能
  • 难度 省选/NOI-
  • 时空限制 2000ms-3000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目背景

    感谢@浮尘ii 提供的一组hack数据

    题目描述

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

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

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

    输入输出格式

    输入格式:

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

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

    再接下来m 行,每行三个非负整数 t,xi,yi。

    如果t=1 ,则表示 Ayu 又回忆起了一个可能埋着玩偶的点 (xi,yi) 。

    如果t=2 ,则表示 Ayu 询问如果她在点 (xi,yi) ,那么在已经回忆出来的点里,离她近的那个点有多远

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    2 3 
    1 1 
    2 3 
    2 1 2 
    1 3 3 
    2 4 2
    输出样例#1: 复制
    1 
    2

    说明

    n,m<=300 000

    xi,yi<=1 000 000

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。