SJY摆棋子
时间限制：20s 空间限制：128MB
题目描述
这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。
输入格式
第一行两个数 N M
以后M行，每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子
输出格式
对于每个T=2 输出一个最小距离
样例输入
2 3 1 1 2 3 2 1 2 1 3 3 2 4 2
样例输出
1 2
提示
kdtree可以过
题目来源
鸣谢 孙嘉裕