KD-Tree复习笔记(BZOJ1941 & BZOJ2648 & BZOJ4066)

时间:2022-01-23 20:49:07

快一年了都没碰到什么必须用KDT的题目导致模板完全忘光了,重新复习了一下。

K_Dimention_Tree是一种用来处理二维以上问题的数据结构(OI中一般都是二维),本质是二维启发式估价函数实现剪枝(实际上就是暴搜的优化),随机数据是大常数$O(n\log n)$,构造数据是$O(n\sqrt{n})$,但是好像可以过50W。

先说一下实现:

Build() : 对于二维中的一系列点,枚举x坐标中位数的一条直线,直线两边的点分别划为左右子树,下一层枚举y坐标中位数,不断交替进行。

Ins() : 同样x,y坐标交替作为关键字插入,类似平衡数,代码很简短。

Que() : 先求出两棵子树的估价函数,选估价更优的递归下去,然后递归另一个(如果估价比当前答案还要劣则剪枝)。由此可知,估价函数和A-Star中的启发式函数一样,必须保证估价比实际优。

下面分别说一下两个模型的启发式函数:

1.曼哈顿最小值和最大值:

1 int getmn(P a){ int s=0; rep(i,0,1) s+=max(T[i]-a.mx[i],0),s+=max(a.mn[i]-T[i],0); return s; }
2 int getmx(P a){ int s=0; rep(i,0,1) s+=max(abs(T[i]-a.mx[i]),abs(T[i]-a.mn[i])); return s; }

 

2.欧氏距离最大值:

int getmx(P a){ int s=0; rep(i,0,1) s+=sqr(max(abs(T[i]-a.mx[i]),abs(T[i]-a.mn[i]))); return s; }

几个注意点:

1.并不一定需要启发式函数,只需要普通的显然的剪枝,KD树也不一定是求最优化,见下面例题。

2.模板稍长且很容易写错,并且很多时候出错不体现在WA而是TLE,写的时候一定要注意细节。

3.build因为有时是rebuild,所以没有数的地方要返回0(被坑了好多次)

 

下面是例题:

1. BZOJ1941

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=500010,inf=1000000000;
 9 int n,ans=inf,res,rt,F=0;
10 
11 inline void cmin(int &x,int y){ if (y<x) x=y; }
12 inline void cmax(int &x,int y){ if (y>x) x=y; }
13 int abs(int x){ return (x<0) ? -x : x; }
14 
15 struct P{
16     int d[2],mx[2],mn[2],l,r;
17     int& operator [](int x){ return d[x]; }
18     friend bool operator <(P a,P b){ return a[F]<b[F]; }
19     friend int dis(P a,P b){ return abs(a[0]-b[0])+abs(a[1]-b[1]); }
20 }p[N],t[N],T;
21 
22 void upd(int x){
23     int l=t[x].l,r=t[x].r;
24     rep(i,0,1){
25         t[x].mn[i]=t[x].mx[i]=t[x][i];
26         if (l) cmin(t[x].mn[i],t[l].mn[i]),cmax(t[x].mx[i],t[l].mx[i]);
27         if (r) cmin(t[x].mn[i],t[r].mn[i]),cmax(t[x].mx[i],t[r].mx[i]);
28     }
29 }
30 
31 int build(int l,int r,int k){
32     if (l>r) return 0;
33     F=k; int mid=(l+r)>>1;
34     nth_element(p+l,p+mid,p+r+1); t[mid]=p[mid];
35     rep(i,0,1) t[mid].mn[i]=t[mid].mx[i]=t[mid][i];
36     t[mid].l=build(l,mid-1,k^1); t[mid].r=build(mid+1,r,k^1);
37     upd(mid); return mid;
38 }
39 
40 int getmn(P a){ int s=0; rep(i,0,1) s+=max(T[i]-a.mx[i],0),s+=max(a.mn[i]-T[i],0); return s; }
41 int getmx(P a){ int s=0; rep(i,0,1) s+=max(abs(T[i]-a.mx[i]),abs(T[i]-a.mn[i])); return s; }
42 
43 void quemn(int x){
44     int tmp=dis(T,t[x]);
45     if (tmp) res=min(res,tmp);
46     int l=t[x].l,r=t[x].r,dl=inf,dr=inf;
47     if (l) dl=getmn(t[l]); if (r) dr=getmn(t[r]);
48     if (dl<dr) { if (dl<res) quemn(l); if (dr<res) quemn(r); }
49         else { if (dr<res) quemn(r); if (dl<res) quemn(l); }
50 }
51 
52 void quemx(int x){
53     res=max(res,dis(T,t[x]));
54     int l=t[x].l,r=t[x].r,dl=-inf,dr=-inf;
55     if (l) dl=getmx(t[l]); if (r) dr=getmx(t[r]);
56     if (dl>dr) { if (dl>res) quemx(l); if (dr>res) quemx(r); }
57         else { if (dr>res) quemx(r); if (dl>res) quemx(l); }
58 }
59 
60 int que(int f,int x,int y){
61     T[0]=x; T[1]=y;
62     if (f) res=-inf,quemx(rt); else res=inf,quemn(rt);
63     return res;
64 }
65 
66 int main(){
67     freopen("bzoj1941.in","r",stdin);
68     freopen("bzoj1941.out","w",stdout);
69     scanf("%d",&n);
70     rep(i,1,n) scanf("%d%d",&p[i][0],&p[i][1]);
71     rt=build(1,n,0);
72     rep(i,1,n) ans=min(ans,que(1,p[i][0],p[i][1])-que(0,p[i][0],p[i][1]));
73     printf("%d\n",ans);
74     return 0;
75 }

 

2.BZOJ2648

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 typedef long long ll;
 6 using namespace std;
 7 
 8 const int N=1000010,inf=1000000000;
 9 int n,m,F,nd,rt,op,res;
10 
11 inline void cmin(int &x,int y){ if (y<x) x=y; }
12 inline void cmax(int &x,int y){ if (y>x) x=y; }
13 int abs(int x){ return (x<0) ? -x : x; }
14 
15 struct P{
16     int d[2],mn[2],mx[2],l,r;
17     int& operator [](int x){ return d[x]; }
18     friend bool operator <(P a,P b){ return a[F]<b[F]; }
19     friend int dis(P a,P b){ return abs(a[0]-b[0])+abs(a[1]-b[1]); }
20 }p[N],t[N],a;
21 
22 void upd(int x){
23     int l=t[x].l,r=t[x].r;
24     rep(i,0,1){
25         t[x].mn[i]=t[x].mx[i]=t[x][i];
26         if (l) cmin(t[x].mn[i],t[l].mn[i]),cmax(t[x].mx[i],t[l].mx[i]);
27         if (r) cmin(t[x].mn[i],t[r].mn[i]),cmax(t[x].mx[i],t[r].mx[i]);
28     }
29 }
30 
31 int build(int l,int r,int k){
32     if (l>r) return 0;
33     F=k; int mid=(l+r)>>1;
34     nth_element(p+l,p+mid,p+r+1); t[mid]=p[mid];
35     rep(i,0,1) t[mid].mn[i]=t[mid].mx[i]=t[mid][i];
36     t[mid].l=build(l,mid-1,k^1); t[mid].r=build(mid+1,r,k^1);
37     upd(mid); return mid;
38 }
39 
40 void ins(int &x,int k){
41     if (!x) { t[x=++nd]=a; upd(x); return; }
42     if (a[k]<=t[x][k]) ins(t[x].l,k^1); else ins(t[x].r,k^1);
43     upd(x);
44 }
45 
46 int get(int x){
47     int s=0;
48     rep(i,0,1) s+=max(a[i]-t[x].mx[i],0)+max(t[x].mn[i]-a[i],0);
49     return s;
50 }
51 
52 void que(int x){
53     res=min(res,dis(t[x],a));
54     int l=t[x].l,r=t[x].r,dl=inf,dr=inf;
55     if (l) dl=get(l); if (r) dr=get(r);
56     if (dl<dr) { if (dl<res) que(l); if (dr<res) que(r); }
57         else { if (dr<res) que(r); if (dl<res) que(l); }
58 }
59 
60 int main(){
61     scanf("%d%d",&n,&m);
62     rep(i,1,n) scanf("%d%d",&p[i][0],&p[i][1]);
63     rt=build(1,n,0); nd=n;
64     rep(i,1,m){
65         scanf("%d%d%d",&op,&a[0],&a[1]);
66         if (op==1) ins(rt,0); else res=inf,que(rt),printf("%d\n",res);
67     }
68     return 0;
69 }

3.BZOJ4066

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define rep(i,l,r) for (int i=l; i<=r; i++)
 5 #define G x1,y1,x2,y2,t[x].mn[0],t[x].mn[1],t[x].mx[0],t[x].mx[1]
 6 typedef long long ll;
 7 using namespace std;
 8 
 9 const int N=200010;
10 int n,op,F,rt,m=10000;
11 ll v,ans,cnt,x1,y1,x2,y2;
12 
13 inline void cmin(int &x,int y){ if (y<x) x=y; }
14 inline void cmax(int &x,int y){ if (y>x) x=y; }
15 
16 bool in(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2)
17 { return x1<=X1 && X2<=x2 && y1<=Y1 && Y2<=y2;}
18 bool out(int x1,int y1,int x2,int y2,int X1,int Y1,int X2,int Y2)
19 { return x1>X2 || x2<X1 || y1>Y2 || y2<Y1; }
20 
21 struct P{
22     int d[2],mn[2],mx[2],l,r,v; ll sm;
23     int& operator [](int x){ return d[x]; }
24     friend bool operator <(P a,P b){ return a[F]<b[F]; }
25 }T,p[N],t[N];
26 
27 void upd(int x){
28     int l=t[x].l,r=t[x].r;
29     rep(i,0,1){
30         t[x].mn[i]=t[x].mx[i]=t[x][i];
31         if (l) cmin(t[x].mn[i],t[l].mn[i]),cmax(t[x].mx[i],t[l].mx[i]);
32         if (r) cmin(t[x].mn[i],t[r].mn[i]),cmax(t[x].mx[i],t[r].mx[i]);
33     }
34     t[x].sm=t[l].sm+t[r].sm+t[x].v;
35 }
36 
37 int build(int l,int r,int k){
38     if (l>r) return 0;
39     F=k; int mid=(l+r)>>1;
40     nth_element(p+l,p+mid,p+r+1); t[mid]=p[mid];
41     t[mid].l=build(l,mid-1,k^1); t[mid].r=build(mid+1,r,k^1);
42     upd(mid); return mid;
43 }
44 
45 void ins(int &x,int k){
46     if (!x) { t[x=++cnt]=T; upd(x); return; }
47     if (T[0]==t[x][0] && T[1]==t[x][1]){ t[x].v+=T.v; t[x].sm+=T.v; return; }
48     if (T[k]<t[x][k]) ins(t[x].l,k^1); else ins(t[x].r,k^1);
49     upd(x);
50 }
51 
52 ll que(int x,int x1,int y1,int x2,int y2){
53     if (!x) return 0; ll tmp=0,l=t[x].l,r=t[x].r;
54     if (in(G)) return t[x].sm; if (out(G)) return 0;
55     if (in(x1,y1,x2,y2,t[x][0],t[x][1],t[x][0],t[x][1])) tmp+=t[x].v;
56     tmp+=que(l,x1,y1,x2,y2)+que(r,x1,y1,x2,y2);
57     return tmp;
58 }
59 
60 int main(){
61     freopen("bzoj4066.in","r",stdin);
62     freopen("bzoj4066.out","w",stdout);
63     scanf("%d",&n);
64     while (1){
65         scanf("%d",&op);
66         if (op==3) break;
67         if (op==1){
68             scanf("%lld%lld%lld",&x1,&y1,&v);
69             T[0]=x1^ans; T[1]=y1^ans; T.v=v^ans; ins(rt,0);
70             if (cnt==m){
71                 rep(i,1,cnt) p[i]=t[i]; m+=10000; rt=build(1,cnt,0);
72             }
73         }else{
74             scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
75             x1^=ans; y1^=ans; x2^=ans; y2^=ans;
76             printf("%lld\n",ans=que(rt,x1,y1,x2,y2));
77         }
78     }
79     return 0;
80 }

4.崂山百花蛇草水:见LOJ代码