Lockey的瞎理解
抄了一遍板子又水了俩题，感觉对KD-tree 稍稍理解了一点儿，唠叨一下（二维的KD-tree），如有错误请指出（Lockey 洗脸恭听）
普通平衡树维护的是一维的序列，但对于二维（可以建平衡树套平衡树，但不好维护）甚至多维就凉了，所以就用到了KD-tree这一神奇的数据结构（伪装“砖家”ing～）
KD-tree 将二维的平面分别按x,y轮流划分，将平面建成一棵BST ，然后查找，在树中维护当前点所代表的值以及记录以它为根的子树信息（最大值，最小值，值的和，等等），
而通过当前点的信息我们可以判断是否需要往下走，以此来进行查找统计，当然这个判断条件一定要正确（百分百保证不能往下走或需要往下走）
为了优化时间，KD-tree中进行剪枝也比较重要，如要统计最大值，可以先用估价函数估计该点两个儿子的估值，比较两个儿子，走估值比较大的儿子，如此，等这个儿子回溯回来，最大值有可能被更新，使得原本大于原来的最大值的而可以走的另一个儿子，现在小于当前最大值而不能走，从而实现剪枝
Hide and Seek（中文名：捉迷藏）
KD-tree板子题一道
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; int n,maximum,minimum,sz,now,ans; struct Point{ int x[2]; }sour[510000]; int comp(Point a,Point b){ return a.x[now]<b.x[now]; } int dis(Point a,Point b){ return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]); } struct KD_Tree{ KD_Tree *ch[2]; Point ponit; int maxn[2],minn[2]; void redef(Point a){ ponit=a,minn[0]=maxn[0]=a.x[0],minn[1]=maxn[1]=a.x[1],ch[0]=ch[1]=NULL; } void update(KD_Tree *a){ minn[0]=min(minn[0],a->minn[0]),maxn[0]=max(maxn[0],a->maxn[0]); minn[1]=min(minn[1],a->minn[1]),maxn[1]=max(maxn[1],a->maxn[1]); } void pushup(){ if(ch[0]) update(ch[0]); if(ch[1]) update(ch[1]); } int calc_min(Point a){ return max(minn[0]-a.x[0],0)+max(a.x[0]-maxn[0],0)+max(minn[1]-a.x[1],0)+max(a.x[1]-maxn[1],0); } int calc_max(Point a){ return max(abs(a.x[0]-minn[0]),abs(a.x[0]-maxn[0]))+max(abs(a.x[1]-minn[1]),abs(a.x[1]-maxn[1])); } }*root,tr[510000]; void build(KD_Tree *&p,int l,int r,int d){ if(l>r) return; p=tr+(sz++),now=d; nth_element(sour+l,sour+((l+r)/2),sour+(r+1),comp); p->redef(sour[((l+r)/2)]); build(p->ch[0],l,((l+r)/2)-1,d^1); build(p->ch[1],((l+r)/2)+1,r,d^1); p->pushup(); } void query_max(KD_Tree *p,Point cmp){ if(p==NULL) return; maximum=max(dis(p->ponit,cmp),maximum); int Dis[2]={p->ch[0]==NULL?0:p->ch[0]->calc_max(cmp),p->ch[1]==NULL?0:p->ch[1]->calc_max(cmp)}; int first=Dis[0]>Dis[1]?0:1; if(Dis[first]>maximum) query_max(p->ch[first],cmp); if(Dis[first^1]>maximum) query_max(p->ch[first^1],cmp); } void query_min(KD_Tree *p,Point cmp){ if(p==NULL) return; if(dis(p->ponit,cmp)) minimum=min(dis(p->ponit,cmp),minimum); int Dis[2]={p->ch[0]==NULL?0x7f7f7f7f:p->ch[0]->calc_min(cmp),p->ch[1]==NULL?0x7f7f7f7f:p->ch[1]->calc_min(cmp)}; int first=Dis[0]<Dis[1]?0:1; if(Dis[first]<minimum) query_min(p->ch[first],cmp); if(Dis[first^1]<minimum) query_min(p->ch[first^1],cmp); } int query_max(Point cmp){ maximum=0,query_max(root,cmp); return maximum; } int query_min(Point cmp){ minimum=0x7fffffff,query_min(root,cmp); return minimum; } int main(){ scanf("%d",&n); ans=0x7f7f7f7f; for(int i=1;i<=n;i++) scanf("%d%d",&sour[i].x[0],&sour[i].x[1]); build(root,1,n,0); for(int i=1;i<=n;i++){ ans=min(ans,query_max(sour[i])-query_min(sour[i])); } printf("%d ",ans); }
巧克力王国
每个点记录以它为根的子树中x,y最大值最小值以及子树中的h和，为什么要这样呢？因为如果只记录最小值无法在有负数是判断，只记录最大值和最小值，会超时
而记录了最大值与最小值不仅可以百分百确定是否往下走，而且能够判断这棵子树中的所有巧克力是不是全都能接受，如果全都能接受的话，就不需要往下走了，直接 $ans+= a*sumx+b*sumy $,然后return即可
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; #define ll long long int n,m,sz,now; ll sum,a,b,c; struct Cho{ ll x[2],h; }chok[51000]; int comp(Cho a,Cho b){ return a.x[now]<b.x[now]; } struct KD_Tree{ KD_Tree *ch[2]; Cho qiao; ll minn[2],maxn[2],hsum; void redef(Cho a){ qiao=a,minn[0]=maxn[0]=a.x[0],minn[1]=maxn[1]=a.x[1],ch[0]=ch[1]=NULL; hsum=a.h; } void update(KD_Tree *a){ minn[0]=min(minn[0],a->minn[0]); minn[1]=min(minn[1],a->minn[1]); maxn[0]=max(maxn[0],a->maxn[0]); maxn[1]=max(maxn[1],a->maxn[1]); hsum+=a->hsum; } void pushup(){ if(ch[0]) update(ch[0]); if(ch[1]) update(ch[1]); } ll calc_C(){ return min(a*minn[0],a*maxn[0])+min(b*minn[1],b*maxn[1]); } }*root,tr[51000]; void build(KD_Tree *&p,int l,int r,int d){ if(l>r) return; p=tr+(sz++),now=d; nth_element(chok+l,chok+((l+r)/2),chok+(r+1),comp); p->redef(chok[(l+r)/2]); build(p->ch[0],l,(l+r)/2-1,d^1); build(p->ch[1],(l+r)/2+1,r,d^1); p->pushup(); } int judge(KD_Tree *p){ ll x=a>0?p->maxn[0]:p->minn[0], y=b>0?p->maxn[1]:p->minn[1]; return a*x+b*y<c; } void query_sum(KD_Tree *p){ if(p==NULL) return; if(judge(p)){ sum+=p->hsum; return; } if((p->qiao.x[0]*a+p->qiao.x[1]*b)<c) sum+=p->qiao.h; ll Dis[2]={p->ch[0]==NULL?0:p->ch[0]->calc_C(),p->ch[1]==NULL?0:p->ch[1]->calc_C()}; if(Dis[0]<c&&p->ch[0]) query_sum(p->ch[0]); if(Dis[1]<c&&p->ch[1]) query_sum(p->ch[1]); } void query_sum(){ sum=0; query_sum(root); } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%lld%lld%lld",&chok[i].x[0],&chok[i].x[1],&chok[i].h); build(root,1,n,0); while(m--){ scanf("%lld%lld%lld",&a,&b,&c); query_sum(); printf("%lld ",sum); } }
JZPFAR
题意是说要找距离第k大，一开始我是想维护一个大根堆，从堆顶pop，一直删k-1次后，堆顶的位置就是ans，然后发现为了剪枝我们需要找到当前堆中第K大的距离，与要插入的值（或估值）比较，如果比当前第K大还小就不插入，理论上好像能行，但是操作起来有些麻烦
因此改用了小根堆
对于每组询问，维护一个大小为Ki的小根堆，当大小小于Ki时见谁插谁；当大小等于Ki，只有在当前的距离（或估值）大于堆顶时才可加入，且每加入一个就pop一个保持堆的大小。
最后，大小为K的堆表示，所有距离中最大的K个距离，而堆顶就是第K大
PS： 应该可以用手写堆优化，但没打对，好像是死循环，改了一下午，有时间要多多的练习一下手写堆
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; #define INF 0x7fffffff #define int long long int n,m,sz,now,px,py,pk; int top;//大根堆 struct Queue{ int val,pos; Queue(int a=0,int b=0){val=a,pos=b;} bool operator < (const Queue &a) const{ return val==a.val?pos<a.pos:val>a.val; } }; priority_queue<Queue>q; struct node{ int x[2],id; }sour[110000]; int comp(node a,node b){return a.x[now]<b.x[now];} int multi(int a){return a*a;} struct KD_Tree{ KD_Tree *ch[2]; node po; int maxn[2],minn[2]; void redef(node a){ po=a,maxn[0]=minn[0]=a.x[0],maxn[1]=minn[1]=a.x[1],ch[0]=ch[1]=NULL; } void update(KD_Tree *a){ maxn[0]=max(maxn[0],a->maxn[0]),minn[0]=min(minn[0],a->minn[0]); maxn[1]=max(maxn[1],a->maxn[1]),minn[1]=min(minn[1],a->minn[1]); } void pushup(){ if(ch[0]) update(ch[0]); if(ch[1]) update(ch[1]); } int clac_max(){ return max(multi(maxn[0]-px),multi(px-minn[0]))+max(multi(maxn[1]-py),multi(py-minn[1])); } }*root,tr[110000]; int len(KD_Tree *p){ return multi(p->po.x[0]-px)+multi(p->po.x[1]-py); } void build(KD_Tree *&p,int l,int r,int d){ if(l>r) return; p=tr+(sz++),now=d; nth_element(sour+l,sour+((l+r)/2),sour+r+1,comp); p->redef(sour[(l+r)/2]); build(p->ch[0],l,(l+r)/2-1,d^1); build(p->ch[1],(l+r)/2+1,r,d^1); p->pushup(); } void query_kth(KD_Tree *p){ if(p==NULL) return; if(top<pk||len(p)>q.top().val||(len(p)==q.top().val&&p->po.id<q.top().pos)){ q.push(Queue(len(p),p->po.id)); if(q.size()>pk) q.pop(); } int Dis[2]={ p->ch[0]==NULL?-INF:p->ch[0]->clac_max(), p->ch[1]==NULL?-INF:p->ch[1]->clac_max() }; int first=Dis[0]>Dis[1]?0:1; if(q.size()<pk||Dis[first]>=q.top().val){ query_kth(p->ch[first]); } if(q.size()<pk||Dis[first^1]>=q.top().val){ query_kth(p->ch[first^1]); } } void query_kth(){ while(q.size()) q.pop(); query_kth(root); } signed main(){ scanf("%lld",&n); for(int i=1;i<=n;i++) scanf("%lld%lld",&sour[i].x[0],&sour[i].x[1]),sour[i].id=i; build(root,1,n,0); scanf("%lld",&m); while(m--){ scanf("%lld%lld%lld",&px,&py,&pk); query_kth(); printf("%lld ",q.top().pos); } }
K远点对
求距离第K远的点对的距离，和上一题一样，只不过小根堆维护的是全局第K大，不需要再每次清空了，
for循环枚举所有的点作为一端，再走一遍就行，注意（1，2）和（2，1）是同一点对，只能算一次
#include<iostream> #include<cstdio> #include<algorithm> #include<queue> using namespace std; #define INF 0x7fffffff #define ll long long ll n,m,sz,now,px,py,yxm; struct Queue{ ll val; Queue(ll a=0){val=a;} bool operator < (const Queue &a) const{ return val>a.val; } }; priority_queue<Queue>q; struct node{ ll x[2],id; }sour[110000]; ll comp(node a,node b){return a.x[now]<b.x[now];} ll multi(ll a){return a*a;} struct KD_Tree{ KD_Tree *ch[2]; node po; ll maxn[2],minn[2]; void redef(node a){ po=a,maxn[0]=minn[0]=a.x[0],maxn[1]=minn[1]=a.x[1],ch[0]=ch[1]=NULL; } void update(KD_Tree *a){ maxn[0]=max(maxn[0],a->maxn[0]),minn[0]=min(minn[0],a->minn[0]); maxn[1]=max(maxn[1],a->maxn[1]),minn[1]=min(minn[1],a->minn[1]); } void pushup(){ if(ch[0]) update(ch[0]); if(ch[1]) update(ch[1]); } ll clac_max(){ return max(multi(maxn[0]-px),multi(px-minn[0]))+max(multi(maxn[1]-py),multi(py-minn[1])); } }*root,tr[110000]; ll len(KD_Tree *p){ return multi(p->po.x[0]-px)+multi(p->po.x[1]-py); } void build(KD_Tree *&p,ll l,ll r,ll d){ if(l>r) return; p=tr+(sz++),now=d; nth_element(sour+l,sour+((l+r)/2),sour+r+1,comp); p->redef(sour[(l+r)/2]); build(p->ch[0],l,(l+r)/2-1,d^1); build(p->ch[1],(l+r)/2+1,r,d^1); p->pushup(); } ll judge(KD_Tree *p){ return q.size()<m||len(p)>=q.top().val; } void query_kth(KD_Tree *p){ if(p==NULL) return; if(p->po.id>yxm&&judge(p)){ q.push(Queue(len(p))); if(q.size()>m) q.pop(); } ll Dis[2]={p->ch[0]==NULL?-INF:p->ch[0]->clac_max(),p->ch[1]==NULL?-INF:p->ch[1]->clac_max()}; ll first=Dis[0]>Dis[1]?0:1; if(q.size()<m||Dis[first]>=q.top().val) query_kth(p->ch[first]); if(q.size()<m||Dis[first^1]>=q.top().val) query_kth(p->ch[first^1]); } void query_kth(){ query_kth(root); } signed main(){ scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) scanf("%lld%lld",&sour[i].x[0],&sour[i].x[1]),sour[i].id=i; build(root,1,n,0); for(int i=1;i<=n;i++){ px=sour[i].x[0],py=sour[i].x[1],yxm=sour[i].id; query_kth(); } // while(q.size()) printf("%lld ",q.top().val); }
未完待续～