首页 > 代码库 > 【BZOJ2648】SJY摆棋子 [KD-tree]

【BZOJ2648】SJY摆棋子 [KD-tree]

SJY摆棋子

Time Limit: 20 Sec  Memory Limit: 128 MB
[Submit][Status][Discuss]

Description

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

Input

  第一行两个数 N M
  然后N行,每行2个数 x y,表示初始棋子
  以后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

  N<=500000 , M<=500000

Main idea

  在平面上加入黑点,对于询问一个坐标到其它点的曼哈顿距离中最小的一个。

Source

  这题显然是一道KD-tree的模板题。

  我们来考虑如何估价,由于求的是最小的曼哈顿距离,我们可以这样估价:

  技术分享

  (其实我也并不懂为什么可以这样估,详情可以查询“n+e KDtree在信息学奥赛中的应用”

Code

技术分享
  1 #include<iostream>      2 #include<string>      3 #include<algorithm>      4 #include<cstdio>      5 #include<cstring>      6 #include<cstdlib>      7 #include<cmath>      8 #include<map>    9 using namespace std;   10    11 const int ONE=1000005; 12 const int INF=2147483640; 13  14 int n,m; 15 int t,x,y; 16 int cnt,Ans; 17 int root; 18 int Ran; 19  20 struct power 21 {     22         int l,r; 23         int x,y; 24         int minx,miny; 25         int maxx,maxy; 26 }a[ONE]; 27  28 int get() 29 {     30         int res=1,Q=1;char c;     31         while( (c=getchar())<48 || c>57 )  32         if(c==-)Q=-1;  33         res=c-48;      34         while( (c=getchar())>=48 && c<=57 )     35         res=res*10+c-48;     36         return res*Q;     37 } 38  39 namespace KD 40 { 41         void Update(int i) 42         { 43             if(a[i].l) 44             { 45                 a[i].minx=min(a[i].minx,a[a[i].l].minx);    a[i].miny=min(a[i].miny,a[a[i].l].miny); 46                 a[i].maxx=max(a[i].maxx,a[a[i].l].maxx);    a[i].maxy=max(a[i].maxy,a[a[i].l].maxy);  47             } 48             if(a[i].r) 49             { 50                 a[i].minx=min(a[i].minx,a[a[i].r].minx);    a[i].miny=min(a[i].miny,a[a[i].r].miny); 51                 a[i].maxx=max(a[i].maxx,a[a[i].r].maxx);    a[i].maxy=max(a[i].maxy,a[a[i].r].maxy); 52             } 53         } 54          55         int cmp(const power &a,const power &b) 56         { 57             if(Ran) return a.x<b.x; 58             return a.y<b.y; 59         } 60          61         int Build(int l,int r,int T) 62         { 63             int mid=(l+r)/2; 64             Ran=T; 65             nth_element(a+l, a+mid+1, a+r+1, cmp); 66             if(l<mid) a[mid].l = Build(l,mid-1,T^1); 67             if(mid<r) a[mid].r = Build(mid+1,r,T^1); 68             Update(mid); 69             return mid; 70         } 71 } 72  73 void Update(int &i,int x,int y,int T) 74 { 75         if(!i) 76         { 77             i=++cnt; 78             a[i].x=a[i].minx=a[i].maxx=x; 79             a[i].y=a[i].miny=a[i].maxy=y; 80             return; 81         } 82          83         if(T) 84         { 85             if(x < a[i].x) Update(a[i].l,x,y,T^1); 86             else Update(a[i].r,x,y,T^1); 87             KD::Update(i); 88         } 89         else 90         { 91             if(y < a[i].y) Update(a[i].l,x,y,T^1); 92             else Update(a[i].r,x,y,T^1); 93             KD::Update(i); 94         } 95 } 96  97 int dist(int x1,int y1,int x2,int y2) 98 { 99         return abs(x1-x2)+abs(y1-y2);100 }101 102 int dist(int i,int x,int y)103 {104         return max(a[i].minx-x,0)+max(x-a[i].maxx,0) + max(a[i].miny-y,0)+max(y-a[i].maxy,0);105 }106 107 void Query(int i,int x,int y)108 {109         if(!i) return;110         Ans=min(Ans,dist(x,y , a[i].x,a[i].y));111         int l=dist(a[i].l,x,y);112         int r=dist(a[i].r,x,y);113         if(l<r)114         {115             if(l<=Ans) Query(a[i].l,x,y);116             if(r<=Ans) Query(a[i].r,x,y);117         }118         else119         {120             if(r<=Ans) Query(a[i].r,x,y);121             if(l<=Ans) Query(a[i].l,x,y);122         }123 }124 125 int main()126 {127         n=get();    m=get();128         for(int i=1;i<=n;i++)129         {130             x=get();    y=get();131             a[i].x=a[i].minx=a[i].maxx=x;132             a[i].y=a[i].miny=a[i].maxy=y;133         }134         135         cnt=n;136         root=KD::Build(1,n,1);137         138         for(int i=1;i<=m;i++)139         {140             t=get();    x=get();    y=get();141             if(t==1)142             {143                 n++;144                 a[n].x=a[n].minx=a[n].maxx=x;145                 a[n].y=a[n].miny=a[n].maxy=y;146                 Update(root,x,y,1);147             }148             else149             {150                 Ans=INF;151                 Query(root,x,y);152                 printf("%d\n",Ans);153             }154         }155 }
View Code

 

【BZOJ2648】SJY摆棋子 [KD-tree]