k-d树简单地说就是暴力......
暴力大法好...
然而我不会.....
k-d tree 用输入的点把一个超平面(呃,高维空间)划分成两部分.(k-d树的节点要把它的坐标存下来.)
一个点管辖一个高维空间内的区域.比如说一个点v.
选择v的第d个维度的坐标(不一定x-y-z-...-x-y-z...轮换.可以x-x-y-x-z-z-...),把管辖区域划分为两个部分.
在这个管辖区域内的所有点,如果其第d维坐标比v的第d维坐标小,就划分到左子树,否则划到右子树(或者小于划到右子树,大于划到左子树.可以在同一棵树上混用,比如对于一个点用前者,对于另一个点用后者).
在划分到左子树的点中选择一个点作为左子树的根,它的管辖范围就是它所在的v划分出来的两个部分的其中一个.
右子树同理.
构建的时间复杂度为 $O(n log n)$ (把输入的点随机打乱,一般不会影响树的功能.)
如果要求在线插入,直接暴力,类似于二叉查找树,通过维度的坐标来判断应该往左子树走还是右子树走,然后走到空节点就说明新的节点应该占据这个空节点的位置.单次插入的最坏复杂度为 $O(n)$ 并且不保证均摊复杂度. 即,总的复杂度可能达到 $O(nk)$ , $k$ 是插入点数, $n$ 是0点数总和.
如果像替罪羊树那样强行重构很不平衡(左右节点数之比约为2:1到4:1)的子树,那么可以达到在线 $O(nlogn)$. 重构方法就是把子树的所有点取出来,随机打乱,然后再插回去.
感觉上,对于每一个点最好再用随机的方法做一个等号判断,即如果坐标相等应该被分到左边还是右边.这样应该可以完全防止插入操作被卡.
对于k-d树的查询,一样是暴力搜索剪枝,具体情况具体分析.
AC BZOJ 2648
1 #include <cstdio>
2 #include <fstream>
3 #include <iostream>
4
5 #include <cstdlib>
6 #include <cstring>
7 #include <algorithm>
8 #include <cmath>
9
10 #include <queue>
11 #include <vector>
12 #include <map>
13 #include <set>
14 #include <stack>
15 #include <list>
16
17 typedef unsigned int uint;
18 typedef long long int ll;
19 typedef unsigned long long int ull;
20 typedef double db;
21 typedef long double ldb;
22
23 using namespace std;
24
25 inline int getint()
26 {
27 int res=0;
28 char c=getchar();
29 bool mi=false;
30 while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
31 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
32 return mi ? -res : res;
33 }
34 inline ll getll()
35 {
36 ll res=0;
37 char c=getchar();
38 bool mi=false;
39 while(c<'0' || c>'9') mi=(c=='-'),c=getchar();
40 while('0'<=c && c<='9') res=res*10+c-'0',c=getchar();
41 return mi ? -res : res;
42 }
43
44 //==============================================================================
45 //==============================================================================
46 //==============================================================================
47 //==============================================================================
48
49
50 const int INF=(1<<30)-1;
51
52 struct node*nil;
53 struct node
54 {
55 int p[2]; //location
56 node*s[2]; //sub trees
57 int l[2][2]; //first D:x/y second d:left(bottom)/right(top)
58
59 node(){ }
60
61 bool leftof(node*x,int d)
62 { return p[d]<x->p[d]; }
63
64 void update(node*f)
65 {
66 l[0][0]=min(l[0][0],f->p[0]);
67 l[0][1]=max(l[0][1],f->p[0]);
68 l[1][0]=min(l[1][0],f->p[1]);
69 l[1][1]=max(l[1][1],f->p[1]);
70 }
71
72 int dist(int x,int y)
73 {
74 int xl=max(l[0][0]-x,0);
75 int xr=max(x-l[0][1],0);
76 int yl=max(l[1][0]-y,0);
77 int yr=max(y-l[1][1],0);
78 return max(xl,xr)+max(yl,yr);
79 }
80 };
81
82 int ncnt=10000;
83 node*nt;
84 node*newnode(int x,int y)
85 {
86 if(ncnt==10000) { ncnt=0; nt=new node[10000]; }
87 nt->p[0]=x; nt->p[1]=y;
88 nt->s[0]=nt->s[1]=nil;
89 nt->l[0][0]=nt->l[0][1]=nt->p[0];
90 nt->l[1][0]=nt->l[1][1]=nt->p[1];
91 ncnt++; return nt++;
92 }
93
94 node*root;
95
96 void Insert(node*v)
97 {
98 if(root==nil)
99 { root=v; return ; }
100
101 node*x=root;
102 node*t=nil;
103 bool d=0;
104 while(x!=nil)
105 {
106 d^=1;
107 t=x;
108 x->update(v);
109 x=x->s[x->leftof(v,d)];
110 }
111 t->s[t->leftof(v,d)]=v;
112 }
113
114 int n,m;
115
116 inline int abs(int p){ return (p&0x80000000) ? -p : p; }
117
118 int qx,qy;
119 inline int mad(node*x)
120 { return abs(x->p[0]-qx)+abs(x->p[1]-qy); }
121
122 int res;
123 void Query(node*a)
124 {
125 res=min(res,mad(a));
126 if(a->s[0]==a->s[1]) return ;
127 int d[]={ a->s[0]==nil ? INF : a->s[0]->dist(qx,qy),
128 a->s[1]==nil ? INF : a->s[1]->dist(qx,qy) };
129 bool k=d[1]<d[0];
130 Query(a->s[k]);
131 if(d[!k]<res) Query(a->s[!k]);
132 }
133
134 int main()
135 {
136 nil=newnode(0,0);
137 nil->s[0]=nil->s[1]=nil;
138 nil->l[0][0]=nil->l[1][0]=-INF;
139 nil->l[0][1]=nil->l[1][1]=INF;
140 root=nil;
141
142 n=getint();
143 m=getint();
144 for(int i=0;i<n;i++)
145 { int x=getint(); int y=getint(); Insert(newnode(x,y)); }
146
147 for(int d=0;d<m;d++)
148 {
149 int t=getint();
150 qx=getint();
151 qy=getint();
152 if(t==1) Insert(newnode(qx,qy));
153 else { res=INF; Query(root); printf("%d
",res); }
154 }
155
156 return 0;
157 }
好慢好慢啊啊啊.......
为什么我的程序就这么慢TAT
对拍的时候运行时间明明是差不多的啊啊啊.....
这道题没有卡插入,卡询问.....
然后妥妥地T了好多遍.......
询问的剪枝方法: 对于每个点,求出它所引领的子树(包括它自己)的所有点的外接矩形.
如果查询点到这个矩形的距离比当前结果大,就不再深入搜索.(最优化剪枝).
然后就可以A了.....