【BZOJ2716/2648】SJY摆棋子

2014年12月10日4,6836

Description

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

Input

第一行两个数 N M
以后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

kdtree可以过

题解

由于对K-Dtree理解不足。。。题解先挖坑吧。。我参照了zky神的模板

 

  • 空灰冰魂2014年12月26日 上午9:41 回复

    1 2
    0 0
    1 1 -1
    2 -2 1

    #1  
    • hzwer2014年12月26日 下午9:31 回复
      admin

      强。。。

      #11
    • hzwer2014年12月26日 下午9:44 回复
      admin

      天使玩偶坐标都是非负数我就没读入符号

      #11
      • 183572015年1月9日 下午6:26 回复

        我当时貌似是代码挂了,拿你的对拍……233

        #12
      • Sigma_Poet2016年2月18日 下午9:39 回复

        K-DTree最高搞到多少维啊??

        #12
        • Vellan2016年4月17日 下午4:23 回复

          n维

          #13