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

题目1： BZOJ 2716

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

算法讨论：

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

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  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_JUDGE
145 int main() {
146 #ifndef ONLINE_JUDGE
147   freopen("1.in", "r", stdin);
148   freopen("1.out", "w", stdout);
149 #endif
150 
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
", query(Node(x, y)));
161   }
162 
163 #ifndef ONLINE_JUDGE
164   fclose(stdin); fclose(stdout);
165 #endif
166   return 0;
167 }

BZOJ 2716

题目2： BZOJ 1941

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

算法讨论：

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

  1 #include <cstdio>
  2 #include <iostream>
  3 #include <cstring>
  4 #include <cstdlib>
  5 #include <algorithm>
  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
", outans);
178   return 0;
179 }

BZOJ 1941

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

题目大意：

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

算法讨论：

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

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

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

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

代码：

#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <queue>
#include <vector>

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 <ll, vector<ll>, greater<ll> > 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;
}