纪念oi路上第一颗kd-tree
Hide and Seek
说说主要思想，考虑二叉搜索树来统计答案，玄学乱搞的地方就是减枝了。通过不断换维（不一定一直换，只要保证时间空间都尽量优就行），用<algorithm>库中的nth_element来找到中位数式的元素，此元素就是二叉搜索树对应的元素。最大值用A*思想减支，最小值用边界判断。还有值得学习的地方是判断先搜左儿子还是右儿子
/*从直系的直系的学长颓来的板子
*/
#include<algorithm>
#include<cstdio>
#include<iostream>
#include<cmath>
#define MAXN 100010
#define INF 0x7fffffff
using namespace std;
int opt;
struct ww{int wg[2];friend bool operator <(const ww &a,const ww &b){return a.wg[opt]<b.wg[opt];}
}wen[MAXN];
inline int minn(int a,int b){return a<b?a:b; }
inline int maxn(int a,int b){return a>b?a:b; }
int n;
struct KDTREE{int num,root,res;struct TREE{ww wen;int ls,rs;int mx[2],mn[2];#define ls(u) (tr[u].ls)#define rs(u) (tr[u].rs)}tr[MAXN];inline int mht(ww a,TREE b){return abs(a.wg[0]-b.wen.wg[0])+abs(a.wg[1]-b.wen.wg[1]); }inline int mxdis(ww a,TREE b){int x=maxn(abs(a.wg[0]-b.mn[0]),abs(a.wg[0]-b.mx[0]));int y=maxn(abs(a.wg[1]-b.mn[1]),abs(a.wg[1]-b.mx[1]));return x+y;}inline int mndis(ww a,TREE b){//只减掉了在边界外的树枝int x=maxn(b.mn[0]-a.wg[0],0)+maxn(a.wg[0]-b.mx[0],0);int y=maxn(b.mn[1]-a.wg[1],0)+maxn(a.wg[1]-b.mx[1],0);return x+y;}void qw_mx(ww a,int u,int knd){if(!u)return ;int tmp;if((tmp=mht(a,tr[u]))>res)res=tmp;int lch=ls(u),rch=rs(u);if(a.wg[knd]<tr[lch].wen.wg[knd])swap(lch,rch);//if(mxdis(a,tr[lch])>res)qw_mx(a,lch,knd^1);if(mxdis(a,tr[rch])>res)qw_mx(a,rch,knd^1);}int qw_mx(ww a){res=-INF;qw_mx(a,root,0);return res;}void qw_mn(ww a,int u,int knd){//printf("u=%d knd=%d\n",u,knd);if(!u)return ;int tmp;if((tmp=mht(a,tr[u]))<res&&tmp)res=tmp;//cout<<tmp<<endl;int lch=ls(u),rch=rs(u);//cout<<lch<<" "<<rch<<endl;if(a.wg[knd]>tr[lch].wen.wg[knd])swap(lch,rch);//if(mndis(a,tr[lch])<res)qw_mn(a,lch,knd^1);if(mndis(a,tr[rch])<res)qw_mn(a,rch,knd^1);}int qw_mn(ww a){//cout<<a.wg[0]<<" "<<a.wg[1]<<endl;res=INF;qw_mn(a,root,0);//cout<<"STO"<<endl;return res;}void up(int u){if(ls(u))for(int i=0;i<2;++i){tr[u].mn[i]=minn(tr[u].mn[i],tr[ls(u)].mn[i]);tr[u].mx[i]=maxn(tr[u].mx[i],tr[ls(u)].mx[i]);}if(rs(u))for(int i=0;i<2;++i){tr[u].mn[i]=minn(tr[u].mn[i],tr[rs(u)].mn[i]);tr[u].mx[i]=maxn(tr[u].mx[i],tr[rs(u)].mx[i]);}}void build(int &u,int l,int r,int knd){if(r<l)return ;u=++num;opt=knd;int mid=l+r>>1;nth_element(wen+l,wen+mid,wen+r+1);tr[u].wen=wen[mid];for(int i=0;i<2;++i)tr[u].mn[i]=tr[u].mx[i]=wen[mid].wg[i];build(ls(u),l,mid-1,knd^1); build(rs(u),mid+1,r,knd^1);up(u);//cout<<u<<" "<<tr[u].wen.wg[0]<<" "<<tr[u].wen.wg[1]<<endl;//cout<<tr[u].mn[0]<<" "<<tr[u].mn[1]<<" "<<tr[u].mx[0]<<" "<<tr[u].mx[1]<<endl;}void build(){root=num=0;build(root,1,n,0);}
}QwQ;
int ans=INF;
int main(){
// freopen("da.in","r",stdin);scanf("%d",&n);for(int i=1;i<=n;++i)scanf("%d%d",&wen[i].wg[0],&wen[i].wg[1]);QwQ.build();for(int i=1;i<=n;++i){ans=minn(ans,QwQ.qw_mx(wen[i])-QwQ.qw_mn(wen[i]));//cout<<"HHHHHHHHH"<<QwQ.qw_mx(wen[i])<<" "<<QwQ.qw_mn(wen[i])<<endl;}printf("%d\n",ans);
}
巧克力王国
考虑两个减支：最小值比C小，不搞。最大值比C小，直接加上维护的子树权值和
#include<iostream>
#include<cstdio>
#include<algorithm>
#define MAXN 50010
#define INF 0x7fffffff
#define int long long
#define reg register int
using namespace std;
inline int maxn(int a,int b){return a>b?a:b; }
inline int minn(int a,int b){return a<b?a:b; }
inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar(); }while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();return s*w;
}
#define kd (read())
int opt;
struct ww{int wg[2],h;friend bool operator <(const ww &a,const ww &b){return a.wg[opt]<b.wg[opt];}
}wen[MAXN];
struct HH{int a,b,c;}hh;
int n,m;
struct KDTREE{int root,num,res;int zmx,zmn;struct TR{ww wen;int mn[2],mx[2],ls,rs,sm;#define ls(u) (tr[u].ls)#define rs(u) (tr[u].rs)}tr[MAXN];inline int cal(HH x,TR y){return x.a*y.wen.wg[0]+x.b*y.wen.wg[1];}inline void judge(HH x,TR y){reg tmp;zmx=-INF;zmn=INF;tmp=y.mn[0]*x.a+y.mn[1]*x.b;zmx=maxn(zmx,tmp);zmn=minn(zmn,tmp);tmp=y.mn[0]*x.a+y.mx[1]*x.b;zmx=maxn(zmx,tmp);zmn=minn(zmn,tmp);tmp=y.mx[0]*x.a+y.mx[1]*x.b;zmx=maxn(zmx,tmp);zmn=minn(zmn,tmp);tmp=y.mx[0]*x.a+y.mn[1]*x.b;zmx=maxn(zmx,tmp);zmn=minn(zmn,tmp);}void qw_sm(HH x,int u){if(!u)return ;if(cal(x,tr[u])<x.c)res+=tr[u].wen.h;judge(x,tr[ls(u)]);if(zmx<x.c)res+=tr[ls(u)].sm;else if(zmn<x.c)qw_sm(x,ls(u));judge(x,tr[rs(u)]);if(zmx<x.c)res+=tr[rs(u)].sm;else if(zmn<x.c)qw_sm(x,rs(u));}int qw_sm(HH x){res=0;qw_sm(x,root);return res;}void up(int u){if(ls(u)){for(reg i=0;i<2;++i){tr[u].mn[i]=minn(tr[u].mn[i],tr[ls(u)].mn[i]);tr[u].mx[i]=maxn(tr[u].mx[i],tr[ls(u)].mx[i]);}tr[u].sm+=tr[ls(u)].sm; }if(rs(u)){for(reg i=0;i<2;++i){tr[u].mn[i]=minn(tr[u].mn[i],tr[rs(u)].mn[i]);tr[u].mx[i]=maxn(tr[u].mx[i],tr[rs(u)].mx[i]);}tr[u].sm+=tr[rs(u)].sm; }}void build(int &u,int l,int r,int knd){if(r<l)return ;u=++num;opt=knd;int mid=l+r>>1;nth_element(wen+l,wen+mid,wen+r+1);tr[u].wen=wen[mid];tr[u].sm=wen[mid].h;for(reg i=0;i<2;++i)tr[u].mn[i]=tr[u].mx[i]=wen[mid].wg[i];build(ls(u),l,mid-1,knd^1);build(rs(u),mid+1,r,knd^1);up(u);}void build(){root=num=0;build(root,1,n,0);}
}QwQ;
signed main(){
// freopen("da.in","r",stdin);n=kd;m=kd;for(reg i=1;i<=n;++i)wen[i].wg[0]=kd,wen[i].wg[1]=kd,wen[i].h=kd;QwQ.build();for(reg i=1;i<=m;++i){hh.a=kd,hh.b=kd,hh.c=kd;printf("%lld\n",QwQ.qw_sm(hh));}
}