KD-tree 总结

T1:Hide and Seek

题干:

  小猪 $iPig$ 在 $PKU$ 刚上完了无聊的猪性代数课,天资聪慧的 $iPig$ 被这门对他来说无比简单的课弄得非常寂寞,为了消除寂寞感,他决定和他的好朋友 $GiPi$(鸡皮)玩一个更加寂寞的游戏---捉迷藏。 但是,他们觉得,玩普通的捉迷藏没什么意思,还是不够寂寞,于是,他们决定玩寂寞无比的螃蟹版捉迷藏,顾名思义,就是说他们在玩游戏的时候只能沿水平或垂直方向走。一番寂寞的剪刀石头布后,他们决定 $iPig$ 去捉 $GiPi$ 。由于他们都很熟悉 $PKU$ 的地形了,所以 $giPi$ 只会躲在 $PKU$ 内 $n$ 个隐秘地点,显然 $iPig$ 也只会在那 $n$ 个地点内找 $giPi$ 。游戏一开始,他们选定一个地点, $iPig$ 保持不动,然后 $giPi$ 用 $30$ 秒的时间逃离现场(显然, $giPi$ 不会呆在原地)。然后 $iPig$ 会随机地去找 $giPi$ ,直到找到为止。由于 $iPig$ 很懒,所以他到总是走最短的路径,而且,他选择起始点不是随便选的,他想找一个地点,使得该地点到最远的地点和最近的地点的距离差最小。 $iPig$ 现在想知道这个距离差最小是多少。 由于 $iPig$ 现在手上没有电脑,所以不能编程解决这个如此简单的问题,所以他马上打了个电话,要求你帮他解决这个问题。$iPig$ 告诉了你 $PKU$ 的 $n$ 个隐秘地点的坐标,请你编程求出 $iPig$ 的问题。

  输入格式:第一行输入一个整数 $N$ 第 $2~N+1$ 行,每行两个整数 $X$,$Y$,表示第 $i$ 个地点的坐标

  输出格式:一个整数,为距离差的最小值。

题解:

  求两点距离,比较简单地就可以想到用 $K-D tree$来解决。

  这道题要求出距离差,我们就可以用 $K-D tree$ 维护一下矩阵最大值与最小值,不断更新答案即可。

  有一个保证时间复杂度的剪枝;优先搜索更可能更新答案的子树,这样就有可能不再走另一棵子树。

  点一下区间最值判断的估价函数:

  1、最大值:直接寻找最大的曼哈顿距离即可

  2、最小值:判断该点是否在子树管辖的空间内,若确实在,就优先搜索;否则滞后搜索。

  时间复杂度 $Theta(nsqrt{n})$ 。

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define $ 500100
 5 #define inf 0x7fffffff
 6 using namespace std;
 7 int n,ans=inf,now,siz,maxx,minn;
 8 struct node{    int x[2];    }a[$];
 9 inline int abss(int x)     {    return (x<0)?-x:x;    }
10 inline int max(int x,int y){    return (x>y)?x:y;    }
11 inline int min(int x,int y){    return (x<y)?x:y;    }
12 inline int mid(int x,int y){    return (x+y)>>1;    }
13 inline bool cmp(const node &a,const node &b){    
14     return a.x[now]<b.x[now];
15 }
16 inline int dis(node a,node b){
17     return abss(a.x[0]-b.x[0])+abss(a.x[1]-b.x[1]);
18 }
19 inline int read(){
20     int a=0;
21     char s=getchar();
22     while(s>'9'||s<'0')   s=getchar();
23     while(s<='9'&&s>='0') a=(a<<1)+(a<<3)+(s^48), s=getchar();
24     return a;
25 }
26 struct tree{    
27     tree *son[2];
28     node pint;
29     int imax[2],imin[2];
30     inline void init(node a){
31         pint=a; son[0]=son[1]=NULL;
32         imin[0]=imax[0]=a.x[0], imin[1]=imax[1]=a.x[1];
33     }
34     inline void update(tree *a){
35         imin[0]=min(imin[0],a->imin[0]), imin[1]=min(imin[1],a->imin[1]);
36         imax[0]=max(imax[0],a->imax[0]), imax[1]=max(imax[1],a->imax[1]);
37     }
38     inline void pushup(){
39         if(son[0]!=NULL) update(son[0]);
40         if(son[1]!=NULL) update(son[1]);
41     }
42     inline int cal_min(node a){
43         return max(imin[0]-a.x[0],0)+max(a.x[0]-imax[0],0)
44               +max(imin[1]-a.x[1],0)+max(a.x[1]-imax[1],0);
45     }
46     inline int cal_max(node a){
47         return max(abss(a.x[0]-imin[0]),abss(a.x[0]-imax[0]))
48               +max(abss(a.x[1]-imin[1]),abss(a.x[1]-imax[1]));
49     }
50 }*root,sum[$];
51 inline void build(tree *&p,int l,int r,int d){
52     if(l>r) return;
53     p=sum+(siz++), now=d;
54     int mid=(l+r)>>1;
55     nth_element(a+l,a+mid,a+r+1,cmp);
56     p->init(a[mid]);
57     build(p->son[0],l,mid-1,d^1), build(p->son[1],mid+1,r,d^1);
58     p->pushup();
59 }
60 inline void query_max(tree *p,node b){
61     if(p==NULL) return;
62     maxx=max(dis(p->pint,b),maxx);
63     int dis[2];
64     dis[0]=(p->son[0]==NULL)?0:p->son[0]->cal_max(b);
65     dis[1]=(p->son[1]==NULL)?0:p->son[1]->cal_max(b);
66     int opt=dis[0]>dis[1]?0:1;
67     if(dis[opt]>maxx)   query_max(p->son[opt],b);
68     if(dis[opt^1]>maxx) query_max(p->son[opt^1],b);
69 }
70 inline void query_min(tree *p,node b){
71     if(p==NULL) return;
72     if(dis(p->pint,b)) minn=min(minn,dis(p->pint,b));
73     int dis[2];
74     dis[0]=(p->son[0]==NULL)?inf:p->son[0]->cal_min(b);
75     dis[1]=(p->son[1]==NULL)?inf:p->son[1]->cal_min(b);
76     int opt=dis[0]>dis[1]?0:1;
77     if(dis[opt]<minn)   query_min(p->son[opt],b);
78     if(dis[opt^1]<minn) query_min(p->son[opt^1],b);
79 }
80 inline int query_max(node b){
81     maxx=0,   query_max(root,b);
82     return maxx;
83 }
84 inline int query_min(node b){
85     minn=inf, query_min(root,b);
86     return minn;
87 }
88 signed main(){
89     n=read();
90     for(register int i=1;i<=n;++i) a[i].x[0]=read(),a[i].x[1]=read();
91     build(root,1,n,0);
92     for(register int i=1;i<=n;++i) 
93         ans=min(ans,query_max(a[i])-query_min(a[i]));
94     printf("%d
",ans);
95 }
View Code

T2:巧克力王国

题干:

  巧克力王国里的巧克力都是由牛奶和可可做成的。但是并不是每一块巧克力都受王国人民的欢迎,因为大家都不喜欢过于甜的巧克力。对于每一块巧克力,我们设 $x$ 和 $y$ 为其牛奶和可可的含量。由于每个人对于甜的程度都有自己的评判标准,所以每个人都有两个参数 $a$ 和 $b$ ,分别为他自己为牛奶和可可定义的权重,因此牛奶和可可含量分别为 $x$ 和 $y$ 的巧克力对于他的甜味程度即为 $ax + by$。而每个人又有一个甜味限度 $c$,所有甜味程度大于等于 $c$ 的巧克力他都无法接受。每块巧克力都有一个美味值 $h$ 。现在我们想知道对于每个人,他所能接受的巧克力的美味值之和为多少

  输入格式:第一行两个正整数 $n$ 和 $m$ ,分别表示巧克力个数和询问个数;接下来 $n$ 行,每行三个整数 $x$ , $y$ , $h$ ,含义如题目所示;再接下来 $m$ 行,每行三个整数 $a$ , $b$ , $c$ 。

  输出格式:输出 $m$ 行,其中第 $i$ 行表示第 $i$ 个人所能接受的巧克力的美味值之和。

题解:

  这道题要求美味值之和,我们维护一个子树和即可。

  在判断时:若区间的最小值都比那个人的 $c$ 值大, $return$ 掉;若区间的最大值都比那个人的 $c$ 值小, 直接将子树和加到答案上即可。  

  注意 $a$、$b$、$c$ 有可能是负数!!

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define $ 50010
 5 #define inf 0x7fffffffffffffff
 6 #define int long long
 7 using namespace std;
 8 int m,n,now;
 9 struct node{
10     int x[2],c;
11     friend bool operator < (const node &a,const node &b){
12         return a.x[now]<b.x[now];
13     }
14     inline bool judge(int a,int b,int c){
15         return x[0]*a+x[1]*b<c;
16     }
17 }a[$];
18 struct tree{
19     tree *son[2];
20     node pint;
21     int imax[2],imin[2],sum;
22     inline void init(node a){
23         pint=a, son[1]=son[0]=NULL;
24         imin[0]=imax[0]=a.x[0], imax[1]=imin[1]=a.x[1];
25     }
26     inline void update(tree *a){
27         imin[0]=min(imin[0],a->imin[0]), imin[1]=min(imin[1],a->imin[1]);
28         imax[0]=max(imax[0],a->imax[0]), imax[1]=max(imax[1],a->imax[1]);
29     }
30     inline void pushup(){
31         sum=pint.c;
32         if(son[0]!=NULL) update(son[0]), sum+=son[0]->sum;
33         if(son[1]!=NULL) update(son[1]), sum+=son[1]->sum;
34     }
35     inline bool big(int a,int b,int c){
36         return max(max(imax[0]*a+imax[1]*b,imax[0]*a+imin[1]*b),
37                 max(imin[0]*a+imax[1]*b,imin[0]*a+imin[1]*b))<c;
38     }
39     inline bool small(int a,int b,int c){
40         return min(min(imax[0]*a+imax[1]*b,imax[0]*a+imin[1]*b),
41                 min(imin[0]*a+imax[1]*b,imin[0]*a+imin[1]*b))<c;
42     }
43 }*root,sum[$],*siz=sum;
44 inline int max(int x,int y){    return (x>y)?x:y;    }
45 inline int min(int x,int y){    return (x<y)?x:y;    }
46 inline int read(){
47     int a=0,b=1;
48     char s=getchar();
49     while((s>'9'||s<'0')&&s!='-') s=getchar();
50     if(s=='-') b=-b, s=getchar();
51     while(s>='0'&&s<='9') a=(a<<3)+(a<<1)+(s^48), s=getchar();
52     return a*b; 
53 }
54 inline void build(tree *&p,int l,int r,int d){
55     if(l>r) return;
56     p=siz++, now=d;
57     int mid=(l+r)>>1;
58     nth_element(a+l,a+mid,a+r+1);
59     p->init(a[mid]);
60     build(p->son[0],l,mid-1,d^1), build(p->son[1],mid+1,r,d^1);
61     p->pushup();
62 }
63 inline int cal(tree *p,int a,int b,int c){
64     if(p==NULL||(p->small(a,b,c)==0)) return 0;
65     if(p->big(a,b,c))  return p->sum;
66     int val=(p->pint.judge(a,b,c))?p->pint.c:0;
67     return cal(p->son[0],a,b,c)+cal(p->son[1],a,b,c)+val;
68 }
69 signed main(){
70     n=read(); m=read();
71     for(register int i=1;i<=n;++i) 
72         a[i].x[0]=read(), a[i].x[1]=read(), a[i].c=read();
73     build(root,1,n,0);
74     for(register int i=1,x,y,z;i<=m;++i){
75         x=read(), y=read(), z=read();
76         printf("%lld
",cal(root,x,y,z));
77     }
78 }
View Code

T3:JZPFAR

题干:

  平面上有 $n$ 个点。现在有 $m$ 次询问,每次给定一个点 $(px, py)$ 和一个整数 $k$ ,输出 $n$ 个点中离 $(px, py)$ 的距离第 $k$ 大的点的标号。如果有两个(或多个)点距离 $(px, py)$ 相同,那么认为标号较小的点距离较大

  输入格式:第一行,一个整数 $n$,表示点的个数;下面 $n$ 行  ,每行两个整数 $x_i$ ,  $y_i$ ,表示 $n$ 个点的坐标。点的标号按照输入顺序,分别为 $1..n$;下面一行,一个整数 $m$,表示询问个数;下面 $m$ 行,每行三个整数 $px_i$, $py_i$, $k_i$,表示一个询问。

  输出格式: $m$ 行,每行一个整数,表示相应的询问的答案。

题解:

  这道题让求的是欧几里得距离,我们仍然用最大值、最小值的剪枝。

  有一个十分难想的做法:既然让求第 $k$ 大的距离,我们就只维护 $k$ 个即可——开始时放 $k$ 个无意义的最小值,不断插入一个、弹出一个即可

  注意:优先队列的大根堆定义时应将小于号定义为 $val1>val2$ 之类的东西,与我们所认知的相反。。。

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #define $ 100100
 6 #define inf 0x7fffffff
 7 #define int long long
 8 using namespace std;
 9 int m,n,k,now;
10 inline int max(int x,int y){    return (x>y)?x:y;    }
11 inline int min(int x,int y){    return (x<y)?x:y;    }
12 inline int abss(int x)     {    return (x<0)?-x:x;    }
13 struct node{
14     int x[2],t;
15     friend bool operator < (const node &a,const node &b){
16         return a.x[now]<b.x[now];
17     }
18 }a[$];
19 struct tree{
20     tree *son[2];
21     node pint;
22     int imax[2],imin[2];
23     inline void init(node a){
24         pint=a, son[0]=son[1]=NULL;
25         imax[0]=imin[0]=a.x[0], imax[1]=imin[1]=a.x[1];
26     }
27     inline void update(tree *a){
28         imin[0]=min(imin[0],a->imin[0]), imin[1]=min(imin[1],a->imin[1]); 
29         imax[0]=max(imax[0],a->imax[0]), imax[1]=max(imax[1],a->imax[1]);
30     }
31     inline void pushup(){
32         if(son[0]!=NULL) update(son[0]);
33         if(son[1]!=NULL) update(son[1]);
34     }
35     inline int cal(node b){
36         return max((imin[0]-b.x[0])*(imin[0]-b.x[0]),(b.x[0]-imax[0])*(b.x[0]-imax[0]))
37               +max((imin[1]-b.x[1])*(imin[1]-b.x[1]),(b.x[1]-imax[1])*(b.x[1]-imax[1]));
38     }
39 }*root,sum[$],*siz=sum;
40 struct cmp{
41     int dis,t;
42     friend bool operator < (const cmp &a,const cmp &b){
43         if(a.dis!=b.dis) return a.dis>b.dis;
44         return a.t<b.t;
45     }
46 };
47 priority_queue<cmp> q;
48 inline int dis(node a,node b){
49     return (a.x[0]-b.x[0])*(a.x[0]-b.x[0])+(a.x[1]-b.x[1])*(a.x[1]-b.x[1]);
50 }
51 inline void build(tree *&p,int l,int r,int d){
52     if(l>r) return;
53     p=siz++, now=d;
54     int mid=(l+r)>>1;
55     nth_element(a+l,a+mid,a+r+1);
56     p->init(a[mid]);
57     build(p->son[0],l,mid-1,d^1), build(p->son[1],mid+1,r,d^1);
58     p->pushup();
59 }
60 inline void cal(tree *p,node b){
61     if(p==NULL) return;
62     int ds=dis(p->pint,b);
63     if(ds>q.top().dis||(ds==q.top().dis&&p->pint.t<q.top().t))  
64         q.pop(), q.push((cmp){ds,p->pint.t});
65     int dis[2];
66     dis[0]=(p->son[0]==NULL)?0:p->son[0]->cal(b);
67     dis[1]=(p->son[1]==NULL)?0:p->son[1]->cal(b);
68     int opt=(dis[0]>dis[1])?0:1;
69     if(dis[opt]>=q.top().dis)   cal(p->son[opt],b);
70     if(dis[opt^1]>=q.top().dis) cal(p->son[opt^1],b);
71 }
72 signed main(){
73     scanf("%lld",&n);
74     for(register int i=1;i<=n;++i) 
75         scanf("%lld%lld",&a[i].x[0],&a[i].x[1]), a[i].t=i;
76     build(root,1,n,1);
77     scanf("%lld",&m);
78     for(register int i=1,x,y,k,ans,t;i<=m;++i){
79         scanf("%lld%lld%lld",&x,&y,&k); 
80         for(register int j=1;j<=k;++j) q.push((cmp){-1,-1});
81         cal(root,(node){x,y,0});
82         printf("%lld
",q.top().t);
83         while(q.size()) q.pop();
84     }
85 }
View Code

T4:K远点对

题干:

  已知平面内 $N$ 个点的坐标,求欧氏距离下的第 $K$ 远点对。

  输入格式:输入文件第一行为用空格隔开的两个整数 $N$, $K$。接下来 $N$ 行,每行两个整数 $X$ , $Y$ ,表示一个点的坐标。$1 < = N < = 100000$, $1 < = K < = 100$, $K < = N*(N−1)/2$ , $0 < = X, Y < 2^{31}$。

  输出格式:输出文件第一行为一个整数,表示第 $K$ 远点对的距离的平方(一定是个整数)。

题解:

  与 T3 几乎完全相同,就是枚举每一个节点,不断压入队列中即可。

  好像很暴力。。。其实就是 $Theta(nsqrt{n})$ 的。。。

Code:

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<queue>
 5 #define $ 100100
 6 #define int long long
 7 using namespace std;
 8 int m,n,k,now,maxx;
 9 priority_queue< int,vector<int>,greater<int> > q;
10 struct node{
11     int x[2];
12     friend bool operator < (const node &a,const node &b){
13         return a.x[now]<b.x[now];
14     }
15 }a[$];
16 struct tree{
17     tree *son[2];
18     node pint;
19     int imin[2],imax[2];
20     inline void init(node a){
21         pint=a, son[0]=son[1]=NULL;
22         imin[0]=imax[0]=a.x[0], imin[1]=imax[1]=a.x[1];
23     }
24     inline void update(tree *a){
25         imin[0]=min(imin[0],a->imin[0]), imin[1]=min(imin[1],a->imin[1]);
26         imax[0]=max(imax[0],a->imax[0]), imax[1]=max(imax[1],a->imax[1]); 
27     }
28     inline void pushup(){
29         if(son[0]!=NULL) update(son[0]);
30         if(son[1]!=NULL) update(son[1]);
31     }
32     inline int cal(node b){
33         return max((b.x[0]-imin[0])*(b.x[0]-imin[0]),(imax[0]-b.x[0])*(imax[0]-b.x[0]))+
34                max((b.x[1]-imin[1])*(b.x[1]-imin[1]),(imax[1]-b.x[1])*(imax[1]-b.x[1]));
35     }
36 }*root,sum[$],*siz=sum;
37 inline int min(int x,int y){    return (x<y)?x:y;    }
38 inline int max(int x,int y){    return (x>y)?x:y;    }
39 inline int dis(node a,node b){
40     return (a.x[0]-b.x[0])*(a.x[0]-b.x[0])+(a.x[1]-b.x[1])*(a.x[1]-b.x[1]);
41 }
42 inline void build(tree *&p,int l,int r,int d){
43     if(l>r) return;
44     p=siz++, now=d;
45     int mid=(l+r)>>1;
46     nth_element(a+l,a+mid,a+r+1);
47     p->init(a[mid]);
48     build(p->son[0],l,mid-1,d^1), build(p->son[1],mid+1,r,d^1);
49     p->pushup(); 
50 }
51 inline void cal(tree *p,node b){
52     if(p==NULL) return;
53     int ds=dis(p->pint,b);
54     if(ds&&q.top()<ds) q.pop(), q.push(ds);
55     int dis[2];
56     dis[0]=(p->son[0]==NULL)?0:p->son[0]->cal(b);
57     dis[1]=(p->son[1]==NULL)?0:p->son[1]->cal(b);
58     int opt=(dis[0]>dis[1])?0:1;
59     if(dis[opt]>q.top())   cal(p->son[opt],b);
60     if(dis[opt^1]>q.top()) cal(p->son[opt^1],b);
61 }
62 signed main(){
63     scanf("%lld%lld",&n,&k);  k*=2;
64     for(register int i=1;i<=k;++i) q.push(0);
65     for(register int i=1;i<=n;++i)
66         scanf("%lld%lld",&a[i].x[0],&a[i].x[1]);
67     build(root,1,n,1);
68     for(register int i=1;i<=n;++i) cal(root,a[i]);
69     printf("%lld
",q.top());
70 }
View Code
越努力 越幸运
原文地址:https://www.cnblogs.com/OI-zzyy/p/11299658.html