考 \(NOI\) 时不会，感觉很亏。于是学了一上午，写了一晚上。 感觉这东西就是个复杂度玄学的高级暴力 （大雾
\(D\) 就是 \(Dimension\) ，维度的意思。 \(KD-tree\) 就是用来解决多维点的问题。 它可以说是一棵平衡树，但建树时用来比较的东西很奇特。 查询几乎与线段树类似，但更暴力一些。每次查询的复杂度为 \(O(n^{\frac{k-1}{k}})\)
最常见的时平面上点的问题，也就是 \(2D-tree\) 有时它的功能可被树套树或 \(CDQ\) 分治实现，它的时间复杂度不如那两者优。 但是它写起来容易，而且在限制空间或在线时是很好的选择。
大体思路与平衡树类似，但特别的地方是权值的比较——各个维度轮流作为关键字来比较。 所以在建树的过程中需要一个变量来记当前以哪一维为关键字。 之后我们要找一个根节点，然后比根节点小的扔到左子，大的扔到右子，分别递归 那为保证树的平衡，根节点就是中位数咯\(STL\) 有一个高级函数 \(nth \_ element()\) 可以在 \(O(n)\) 实现找第 \(k\) 小的点，并将比它小或大的点分居在它两侧。 借助它就能在 \(O(Knlogn)\) 完成建树了。
插入 \(insert\)与平衡树的插入类似，就是按照比较权值的方法，小的往左子走，大的往右子走。
拍扁重构 \(check+pia+build\)为了保证树的平衡，类似替罪羊树，在插入后判断树是否失衡（即左子或右子的 \(size\) 过大） 如果失衡，就暴力重构这个子树。 具体地，就是先遍历一遍，把子树中所有点都拿出来。然后对这个子树 \(build\) 注意空间的回收利用，可以用一个栈保存删掉的点的地址。
查询 \(query\)与线段树类似，但非常非常暴力。 若整个区间满足条件，就用维护好的有关整个区间的东西；不满足，就分别询问当前点及两个子树。 需要用到剪枝、乱搞等技巧。
首先，为了查询方便，每个节点要记录子树的范围，即子树中各维度的 \(mn\) 和 \(mx\) 然后可以设置估值函数。 根据估值函数的大小我们可以决定进不进某个子树、先进哪个子树等等……
洛谷 \(P4169\) \([Violet]天使玩偶/ SJY 摆棋子\) 求最小曼哈顿距离。
#include<cstdio> #include<iostream> #include<algorithm> #define INF 10000000 using namespace std; int read(){ int x=0; char ch=getchar(); while(!isdigit(ch)) ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x; } const int N = 300005; int n,D; struct data { int d[2]; data() { d[0]=d[1]=0; } data(int x,int y) { d[0]=x; d[1]=y; } bool operator < (const data &b) const{ return d[D]<b.d[D]; } }a[N],b[N*2]; int tot; struct tree{ tree *ch[2]; int mx[2],mn[2],d[2],sz; }pool[N*2],*st[N*2],*root; int cnt,top; tree *New() { return top?st[--top]:&pool[++cnt]; } int mn(tree *p,int i) { return p ? p->mn[i] : INF ; } int mx(tree *p,int i) { return p ? p->mx[i] : -INF ; } int sz(tree *p) { return p ? p->sz : 0 ; } void update(tree *p){ for(int i=0;i<2;i++){ p->mx[i]=max(p->d[i],max(mx(p->ch[0],i),mx(p->ch[1],i))); p->mn[i]=min(p->d[i],min(mn(p->ch[0],i),mn(p->ch[1],i))); } p->sz=1+sz(p->ch[0])+sz(p->ch[1]); } tree *build(data A[],int l,int r,int de){ if(l>r) return NULL; tree *p=New(); int mid=(l+r)>>1; D=de; nth_element(A+l,A+mid,A+r); p->d[0]=A[mid].d[0]; p->d[1]=A[mid].d[1]; p->ch[0]=build(A,l,mid-1,de^1); p->ch[1]=build(A,mid+1,r,de^1); update(p); return p; //别忘了返回值！ } void pia(tree *p){ if(p->ch[0]) pia(p->ch[0]); st[top++]=p; b[++tot].d[0]=p->d[0]; b[tot].d[1]=p->d[1]; if(p->ch[1]) pia(p->ch[1]); } tree *check(tree *p,int de){ if(1.0*sz(p->ch[0])<=0.75*p->sz && 1.0*sz(p->ch[1])<=0.75*p->sz) return p; tot=0; pia(p); return build(b,1,tot,de); } void insert(tree *p,tree *nd,int de){ int f=nd->d[de]>p->d[de]; if(!p->ch[f]) p->ch[f]=nd; else insert(p->ch[f],nd,de^1); p->ch[f]=check(p->ch[f],de^1); update(p); } int getdis(tree *p,data x){ if(!p) return INF; int ret=0; for(int i=0;i<2;i++) ret+=max(0,p->mn[i]-x.d[i])+max(0,x.d[i]-p->mx[i]); return ret; } int ans; void query(tree *p,data x){ if(!p) return; ans=min(ans,abs(p->d[0]-x.d[0])+abs(p->d[1]-x.d[1])); int d0=getdis(p->ch[0],x),d1=getdis(p->ch[1],x); if(d0>=ans && d1>=ans) return; if(d0<d1){ query(p->ch[0],x); if(d1<ans) query(p->ch[1],x); } else{ query(p->ch[1],x); if(d0<ans) query(p->ch[0],x); } } int main() { int m,t,x,y; n=read(); m=read(); for(int i=1;i<=n;i++){ a[i].d[0]=read(); a[i].d[1]=read(); } root=build(a,1,n,0); while(m--){ t=read(); x=read(); y=read(); if(t==1){ tree *nd=New(); nd->sz=1; nd->mn[0]=nd->mx[0]=nd->d[0]=x; nd->mn[1]=nd->mx[1]=nd->d[1]=y; insert(root,nd,0); root=check(root,0); } else{<C ans=INF; data c(x,y); query(root,c); printf("%d\n",ans); } } return 0; }洛谷 \(P4475 巧克力王国\)
没有新插入的点，所以不需要拍扁重构。 查询时临界点就是4个端点： 若它们中最大的 \(<C\) ，则全部满足；若最小的 \(\geq C\) ,则全不满足。 其实这也等价于判断4个点中有几个满足 \(<C\) ，若4个，则全部满足；若0个，则全不满足。
我嫌指针版常数过大，换了数组版，写着或看着都好清爽呀~ 注意 \(long\) \(long\)
#include<cstdio> #include<iostream> #include<algorithm> #define INF 1000000005 #define ll long long using namespace std; int read(){ int x=0,f=1; char ch=getchar(); while(!isdigit(ch) && ch!='-') ch=getchar(); if(ch=='-') f=-1,ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f; } ll lread(){ int f=1; ll x=0; char ch=getchar(); while(!isdigit(ch) && ch!='-') ch=getchar(); if(ch=='-') f=-1,ch=getchar(); while(isdigit(ch)) x=x*10+ch-'0',ch=getchar(); return x*f; } const int N = 500005; int D; struct data{ int d[2],val,id; data() { d[0]=d[1]=val=id=0; } data(int x,int y,int c,int i) { d[0]=x; d[1]=y; val=c; id=i; } bool operator < (const data &b) const{ return d[D]<b.d[D]; } }a[N]; int ch[N][2],mx[N][2],mn[N][2],d[N][2],root; ll val[N],sum[N]; void update(int x){ for(int i=0;i<2;i++){ mx[x][i]=max(d[x][i],max(mx[ch[x][0]][i],mx[ch[x][1]][i])); mn[x][i]=min(d[x][i],min(mn[ch[x][0]][i],mn[ch[x][1]][i])); } sum[x]=val[x]+sum[ch[x][0]]+sum[ch[x][1]]; } int build(int l,int r,int ty){ if(l>r) return 0; int mid=(l+r)>>1; D=ty; nth_element(a+l,a+mid,a+r+1); int x=a[mid].id; ch[x][0]=build(l,mid-1,ty^1); ch[x][1]=build(mid+1,r,ty^1); update(x); return x; } ll ans,A,B,C; ll cal(int x,int y) { return A*x+B*y; } void ask(int x){ if(!x) return; int t=0; if(cal(mn[x][0],mn[x][1])<C) t++; if(cal(mn[x][0],mx[x][1])<C) t++; if(cal(mx[x][0],mn[x][1])<C) t++; if(cal(mx[x][0],mx[x][1])<C) t++; if(t==0) return; if(t==4) { ans+=sum[x]; return; } if(cal(d[x][0],d[x][1])<C) ans+=val[x]; ask(ch[x][0]); ask(ch[x][1]); } int main() { int n,m; n=read(); m=read(); for(int i=1;i<=n;i++){ d[i][0]=read(); d[i][1]=read(); val[i]=lread(); a[i]=data(d[i][0],d[i][1],val[i],i); } for(int i=0;i<=n;i++) { ch[i][0]=ch[i][1]=0; mx[i][0]=mx[i][1]=-INF; mn[i][0]=mn[i][1]=INF; sum[i]=0; } root=build(1,n,0); while(m--){ A=lread(); B=lread(); C=lread(); ans=0; ask(root); printf("%lld\n",ans); } return 0; }转载于:https://www.cnblogs.com/lindalee/p/11215968.html
相关资源：数据结构—成绩单生成器