x-kdtree question

kdtree question

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 輸出一個最小距離

最佳回答：

http://www.cnblogs.com/ljh2000-jump/p/5513620.html