K-D Tree题目泛做（CXJ第二轮）-白红宇

K-D Tree题目泛做（CXJ第二轮）

阅读量：7180 次

发布时间：2019-06-29

本文共 11351 字，大约阅读时间需要 37 分钟。

题目1： BZOJ 2716

题目大意：给出N个二维平面上的点，M个操作，分为插入一个新点和询问到一个点最近点的Manhatan距离是多少。

算法讨论：

K-D Tree 裸题，有插入操作。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6   7 using namespace std;  8   9 const int inf = 1e9; 10 const int K = 2; 11 const int N = 500000 + 5; 12  13 inline int read() { 14   int x = 0; 15   char ch = getchar(); 16  17   while(ch < '0' || ch > '9') ch = getchar(); 18   while(ch <= '9' && ch >= '0') { 19     x = x * 10 + ch - '0'; 20     ch = getchar(); 21   } 22   return x; 23 } 24  25 int n, m, root, D, ans; 26  27 struct Node { 28   int d[K], mn[K], mx[K], l, r, v, sum; 29  30   int & operator [] (int x) { 31     return d[x]; 32   } 33   Node(int x = 0, int y = 0) { 34     l = 0; r = 0; d[0] = x; d[1] = y; 35   } 36   friend bool operator < (Node a, Node b) { 37     return a[D] < b[D]; 38   } 39 }p[N], T[N<<1], tmp; 40  41 void pushup(int k) { 42   Node l = T[T[k].l], r = T[T[k].r]; 43  44   for(int i = 0; i < K; ++ i) { 45     T[k].mn[i] = T[k].mx[i] = T[k][i]; 46     if(T[k].l) { 47       T[k].mn[i] = min(T[k].mn[i], l.mn[i]); 48       T[k].mx[i] = max(T[k].mx[i], l.mx[i]); 49     } 50     if(T[k].r) { 51       T[k].mx[i] = max(T[k].mx[i], r.mx[i]); 52       T[k].mn[i] = min(T[k].mn[i], r.mn[i]); 53     } 54   } 55   //  T[k].sum = T[k].v; 56   //  if(T[k].l) T[k].sum += l.sum; 57   //  if(T[k].r) T[k].sum += r.sum; 58 } 59  60 int build(int l, int r, int nd) { 61   int mid = (l + r) >> 1; 62  63   D = nd; 64   nth_element(p + l, p + mid, p + r + 1); 65   T[mid] = p[mid]; 66   T[mid].l = T[mid].r = 0; 67   for(int i = 0; i < K; ++ i) 68     T[mid].mx[i] = T[mid].mn[i] = T[mid][i]; 69   if(l < mid) 70     T[mid].l = build(l, mid - 1, (nd + 1) % K); 71   if(r > mid) 72     T[mid].r = build(mid + 1, r, (nd + 1) % K); 73   pushup(mid); 74   return mid; 75 } 76  77 void insert(int k, int nd) { 78   if(tmp[nd] >= T[k][nd]) { 79     if(T[k].r) insert(T[k].r, (nd + 1) % K); 80     else { 81       T[k].r = ++ n; 82       T[n] = tmp; 83       for(int i = 0; i < K; ++ i) 84         T[n].mn[i] = T[n].mx[i] = T[n][i]; 85     } 86   } 87   else { 88     if(T[k].l) insert(T[k].l, (nd + 1) % K); 89     else { 90       T[k].l = ++ n; 91       T[n] = tmp; 92       for(int i = 0; i < K; ++ i) 93         T[n].mn[i] = T[n].mx[i] = T[n][i]; 94     } 95   } 96   pushup(k); 97 } 98  99 int getkdis(Node a, Node b) {100   int res = 0;101 102   for(int i = 0; i < K; ++ i)103     res += abs(a[i] - b[i]);104   return res;105 }106 107 int inandout(int k, Node a) {108   int res = 0;109 110   for(int i = 0; i < K; ++ i)111     res += max(0, T[k].mn[i] - a[i]);112   for(int i = 0; i < K; ++ i)113     res += max(0, a[i] - T[k].mx[i]);114   return res;115 }116 117 118 void query(int k, int nd) {119   int d, dl = inf, dr = inf;120 121   d = getkdis(T[k], tmp);122   if(d) ans = min(ans, d);123   if(T[k].l) dl = inandout(T[k].l, tmp);124   if(T[k].r) dr = inandout(T[k].r, tmp);125   if(dl < dr) {126     if(dl < ans) query(T[k].l, (nd + 1) % K);127     if(dr < ans) query(T[k].r, (nd + 1) % K);128   }129   else {130     if(dr < ans) query(T[k].r, (nd + 1) % K);131     if(dl < ans) query(T[k].l, (nd + 1) % K);132   }133 }134 135 int query(Node a) {136   tmp = a; ans = inf;137   query(root, 0);138   return ans;139 }140 141 void insert(Node a) {142   tmp = a; insert(root, 0);143 }144 #define ONLINE_JUDGE145 int main() {146 #ifndef ONLINE_JUDGE147   freopen("1.in", "r", stdin);148   freopen("1.out", "w", stdout);149 #endif150 151   int type, x, y;152 153   n = read(); m = read();154   for(int i = 1; i <= n; ++ i)155     p[i][0] = read(), p[i][1] = read();156   root = build(1, n, 0);//忘记写root等于了。157   for(int i = 1; i <= m; ++ i) {158     type = read(); x = read(); y = read();159     if(type == 1) insert(Node(x, y));160     else printf("%d\n", query(Node(x, y)));161   }162 163 #ifndef ONLINE_JUDGE164   fclose(stdin); fclose(stdout);165 #endif166   return 0;167 }

BZOJ 2716

题目2： BZOJ 1941

题目大意：给出N个点，求对于每个点说，Manhantan距离最远点与最近点的差值最小是多少。

算法讨论：

K-D Tree裸题，注意最近点不能是自己。

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6   7 using namespace std;  8   9 const int N = 500000 + 5; 10 const int inf = 1e9; 11 const int K = 2; 12  13 inline int read() { 14   int x = 0; 15   char ch = getchar(); 16  17   while(ch < '0' || ch > '9') ch = getchar(); 18   while(ch <= '9' && ch >= '0') { 19     x = x * 10 + ch - '0'; 20     ch = getchar(); 21   } 22   return x; 23 } 24  25 int n, root, amax, amin, D; 26  27 struct Node { 28   int d[K], mn[K], mx[K], l, r; 29  30   int & operator [] (int x) { 31     return d[x]; 32   } 33   Node (int x = 0, int y = 0) { 34     l = 0; r = 0; d[0] = x; d[1] = y; 35   } 36   friend bool operator < (Node a, Node b) { 37     return a[D] < b[D]; 38   } 39 }p[N], T[N<<1], tmp; 40  41 void pushup(int k) { 42   Node l = T[T[k].l], r = T[T[k].r]; 43  44   for(int i = 0; i < K; ++ i) { 45     T[k].mn[i] = T[k].mx[i] = T[k][i]; 46     if(T[k].l) { 47       T[k].mx[i] = max(T[k].mx[i], l.mx[i]); 48       T[k].mn[i] = min(T[k].mn[i], l.mn[i]); 49     } 50     if(T[k].r) { 51       T[k].mx[i] = max(T[k].mx[i], r.mx[i]); 52       T[k].mn[i] = min(T[k].mn[i], r.mn[i]); 53     } 54   } 55 } 56  57 int build(int l, int r, int nd) { 58   int mid = (l + r) >> 1; 59  60   D = nd; 61   nth_element(p + l, p + mid, p + r + 1); 62   T[mid] = p[mid]; 63   T[mid].l = T[mid].r = 0; 64   for(int i = 0; i < K; ++ i) 65     T[mid].mn[i] = T[mid].mx[i] = T[mid][i]; 66   if(l < mid) T[mid].l = build(l, mid - 1, (D + 1) % K); 67   if(r > mid) T[mid].r = build(mid + 1, r, (D + 1) % K); 68   pushup(mid); 69   return mid; 70 } 71  72 void insert(int k, int nd) { 73   if(tmp[nd] >= T[k][nd]) { 74     if(T[k].r) insert(T[k].r, (nd + 1) % K); 75     else { 76       T[k].r = ++ n; 77       T[n] = tmp; 78       for(int i = 0; i < K; ++ i) 79         T[n].mx[i] = T[n].mn[i] = T[n][i]; 80     } 81   } 82   else { 83     if(T[k].l) insert(T[k].l, (nd + 1) % K); 84     else { 85       T[k].l = ++ n; 86       T[n] = tmp; 87       for(int i = 0; i < K; ++ i) 88         T[n].mx[i] = T[n].mn[i] = T[n][i]; 89     } 90   } 91   pushup(k); 92 } 93  94 int getkdis(Node a, Node b) { 95   int res = 0; 96  97   for(int i = 0; i < K; ++ i) 98     res += abs(a[i] - b[i]); 99   return res;100 }101 102 int outandin(int k, Node q) {103   int res = 0;104 105   for(int i = 0; i < K; ++ i)106     res += max(0, T[k].mn[i] - q[i]);107   for(int i = 0; i < K; ++ i)108     res += max(0, q[i] - T[k].mx[i]);109   return res;110 }111 112 int outandinmaxx(int k, Node q) {113   int res = 0;114 115   for(int i = 0; i < K; ++ i)116     res += max(abs(T[k].mn[i] - q[i]), abs(T[k].mx[i] - q[i]));117   return res;118 }119 120 void query_maxx(int k, int nd) {121   int d, dl = -inf, dr = -inf;122 123   d = getkdis(T[k], tmp);124   amax = max(d, amax);125   if(T[k].l) dl = outandinmaxx(T[k].l, tmp);126   if(T[k].r) dr = outandinmaxx(T[k].r, tmp);127   if(dl > dr) {128     if(dl > amax) query_maxx(T[k].l, (nd + 1) % K);129     if(dr > amax) query_maxx(T[k].r, (nd + 1) % K);130   }131   else {132     if(dr > amax) query_maxx(T[k].r, (nd + 1) % K);133     if(dl > amax) query_maxx(T[k].l, (nd + 1) % K);134   }135 }136 137 void query_minn(int k, int nd) {138   int d, dl = inf, dr = inf;139 140   d = getkdis(T[k], tmp);141   if(d) amin = min(d, amin);142   if(T[k].l) dl = outandin(T[k].l, tmp);143   if(T[k].r) dr = outandin(T[k].r, tmp);144   if(dl < dr) {145     if(dl < amin) query_minn(T[k].l, (nd + 1) % K);146     if(dr < amin) query_minn(T[k].r, (nd + 1) % K);147   }148   else {149     if(dr < amin) query_minn(T[k].r, (nd + 1) % K);150     if(dl < amin) query_minn(T[k].l, (nd + 1) % K);151   }152 }153 154 void qmax(int l) {155   amax = -inf; tmp = p[l];156   query_maxx(root, 0);157   158 }159 160 void qmin(int l) {161   amin = inf; tmp = p[l];162   query_minn(root, 0);163 }164 165 int main() {166   int outans = inf;167   168   n = read();169   for(int i = 1; i <= n; ++ i) {170     p[i][0] = read(); p[i][1] = read();171   }172   root = build(1, n, 0);173   for(int i = 1; i <= n; ++ i) {174     qmax(i); qmin(i);175     outans = min(outans, amax - amin);176   }177   printf("%d\n", outans);178   return 0;179 }

BZOJ 1941

题目3： BZOJ4520 &&　CQOI 2016 K远点对查询

题目大意：

给出n个二维平面上的点，求第k远的点对距离是多少。(欧几里德距离的平方)

算法讨论：

1、为了防止重复，小根堆里面保存2*K个元素。

2、编程习惯一定要好。同类型比较，减少强制类型转制。在查询欧几里德距离的时候，query中的维度参数是没有用的。

果断要去掉。否则就是TLE和AC的区别。

要区分好查询欧几里德距离和曼哈顿距离时两者的区别。

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             using namespace std;typedef long long ll;const int N = 100000 + 5;const int K = 2;const ll inf = 10000000000000LL;inline int read() { int x = 0; char c = getchar(); while(!isdigit(c)) c = getchar(); while(isdigit(c)) { x = x * 10 + c - '0'; c = getchar(); } return x;}int buf[20];inline void output(ll x) { int p = 0; buf[0] = 0; if(!x) p ++; else { while(x) { buf[p ++] = x % 10; x /= 10; } } for(int i = p - 1; i >= 0; -- i) putchar(buf[i] + '0');}int root, n, kk, D;priority_queue 
             
              , greater
              
                > ans;struct Node { int l, r; ll d[K], mn[K], mx[K]; Node(ll x = 0, ll y = 0) { l = r = 0; d[0] = x; d[1] = y; } ll & operator [] (int x) { return d[x];} friend bool operator < (Node a, Node b) { return a[D] < b[D]; }}p[N], T[N << 1], tmp;void pushup(int k) { Node l = T[T[k].l], r = T[T[k].r]; for(int i = 0; i < K; ++ i) { T[k].mx[i] = T[k].mn[i] = T[k][i]; if(T[k].l) { T[k].mx[i] = max(T[k].mx[i], l.mx[i]); T[k].mn[i] = min(T[k].mn[i], l.mn[i]); } if(T[k].r) { T[k].mx[i] = max(T[k].mx[i], r.mx[i]); T[k].mn[i] = min(T[k].mn[i], r.mn[i]); } }}int build(int l, int r, int nd) { int mid = (l + r) >> 1; D = nd; nth_element(p + l, p + mid, p + r + 1); T[mid] = p[mid]; T[mid].l = T[mid].r = 0; for(int i = 0; i < K; ++ i) T[mid].mx[i] = T[mid].mn[i] = T[mid][i]; if(l < mid) T[mid].l = build(l, mid - 1, (nd + 1) % K); if(r > mid) T[mid].r = build(mid + 1, r, (nd + 1) % K); pushup(mid); return mid;}ll geteulerdis(Node a, Node b) {//竭诚为欧几里德距离服务 ll res = 0; for(int i = 0; i < K; ++ i) res += (a[i] - b[i]) * (a[i] - b[i]); return res;}ll outandineuler(Node a) { ll L = 0; L = max(L, geteulerdis(tmp, Node(a.mx[0], a.mn[1]))); L = max(L, geteulerdis(tmp, Node(a.mx[0], a.mx[1]))); L = max(L, geteulerdis(tmp, Node(a.mn[0], a.mn[1]))); L = max(L, geteulerdis(tmp, Node(a.mn[0], a.mx[1]))); return L;}void query(int k) { ll d, dl = -inf, dr = -inf; d = geteulerdis(T[k], tmp); if(d > ans.top()) { ans.pop(); ans.push(d); } if(T[k].l) dl = outandineuler(T[T[k].l]); if(T[k].r) dr = outandineuler(T[T[k].r]); if(dl > dr) { if(dl > ans.top()) query(T[k].l); if(dr > ans.top()) query(T[k].r); } else { if(dr > ans.top()) query(T[k].r); if(dl > ans.top()) query(T[k].l); }}void Q(int i) { tmp = p[i]; query(root);}int main() { n = read(); kk = read(); for(int i = 1; i <= 2 * kk; ++ i) ans.push(0); for(int i = 1; i <= n; ++ i) { p[i][0] = read(); p[i][1] = read(); } root = build(1, n, 0); for(int i = 1; i <= n; ++ i) Q(i); output(ans.top()); return 0;}