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

Solution

K-D Tree模板题，注意不替罪羊重构的话会TLE

Code

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 #include
         
            6 #define N (1000000+1000)  7 #define INF 0x7fffffff  8 using namespace std;  9  10 int n,m,D,ans,opt,x,y,Root; 11 double alpha=0.75; 12  13 struct Node 14 { 15     int d[2],Max[2],Min[2],lson,rson,size; 16     bool operator < (const Node &a) const {
   return d[D]
          
           r) return 0; 58 int mid=(l+r)>>1,now=NewNode(); 59 D=opt; nth_element(p+l,p+mid,p+r+1); 60 Tree[now]=p[mid]; Tree[now].size=1; 61 Tree[now].lson=Build(opt^1,l,mid-1); 62 Tree[now].rson=Build(opt^1,mid+1,r); 63 Update(now); 64 return now; 65 } 66 int Get_min(int now) 67 { 68 int ans=0; 69 for (int i=0; i<=1; ++i) 70 { 71 ans+=max(0,T.d[i]-Tree[now].Max[i]); 72 ans+=max(0,Tree[now].Min[i]-T.d[i]); 73 } 74 return ans; 75 } 76 void Query(int now) 77 { 78 ans=min(ans,abs(T.d[0]-Tree[now].d[0])+abs(T.d[1]-Tree[now].d[1])); 79 int ls=Tree[now].lson,rs=Tree[now].rson,lans=INF,rans=INF; 80 if (ls) lans=Get_min(ls); 81 if (rs) rans=Get_min(rs); 82 if (lans
           
            alpha*Tree[now].size || Tree[rs].size>alpha*Tree[now].size)105 {106 Dfs(now,1);107 now=Build(opt,1,Tree[now].size);108 }109 }110 void Insert(int &now,int x,int opt)111 {112 if (Tree[x].d[opt]<=Tree[now].d[opt])113 {114 if (Tree[now].lson) Insert(Tree[now].lson,x,opt^1);115 else Tree[now].lson=x;116 }117 else118 {119 if (Tree[now].rson) Insert(Tree[now].rson,x,opt^1);120 else Tree[now].rson=x;121 }122 Update(now); Check(now,opt);123 }124 }KDT;125 126 int main()127 {128 scanf("%d%d",&n,&m);129 for (int i=1; i<=n; ++i)130 {131 scanf("%d%d",&x,&y);132 p[i].d[0]=x; p[i].d[1]=y;133 }134 Root=KDT.Build(0,1,n);135 for (int i=1; i<=m; ++i)136 {137 scanf("%d%d%d",&opt,&x,&y);138 if (opt==1)139 {140 int t=NewNode();141 KDT.Tree[t]=Node(x,y);142 KDT.Tree[t].size=1;143 KDT.Insert(Root,t,0);144 }145 else146 {147 T.d[0]=x; T.d[1]=y; ans=INF;148 KDT.Query(Root);149 printf("%d\n",ans);150 }151 }152 }