天使玩偶
Ayu 在七年前曾经收到过一个天使玩偶，当时她把它当作时间囊埋在了地下。而七年后 的今天，Ayu 却忘了她把天使玩偶埋在了哪里，所以她决定仅凭一点模糊的记忆来寻找它。
我们把 Ayu 生活的小镇看作一个二维平面坐标系，而 Ayu 会不定时地记起可能在某个点 (x，y) 埋下了天使玩偶；或者 Ayu 会询问你，假如她在 (x,y) ，那么她离近的天使玩偶可能埋下的地方有多远。
因为 Ayu 只会沿着平行坐标轴的方向来行动，所以在这个问题里我们定义两个点之间的距离为dist(A,B)=|Ax-Bx|+|Ay-By|。其中 Ax 表示点 A的横坐标，其余类似。
n,m<=300 000
xi,yi<=1 000 000
分析
kd-tree模板题。
首先依次按照每一维(即先按照x，再按照y，再按照x…多维同理)将点存在一棵二叉树中：
先求出以当前维数为关键字的中间点是谁(用到nth_element这个函数，可以直接把排名为k的放在第k位上，不保证其他有序:nth_element(a+1,a+k,a+1+n,cmp))
为了一会儿查询中求估价函数方便，需要记录一下当前节点的子树中各维的极值(max,min)插入操作插入就按照每个维度往左右子树插就行......可是令人绝望的是,这样子插了若干次之后,可能原树就被退化成一个近似于链的东西了.这个时候,我们就要利用替罪羊树的思想,设一个α=0.75,如果对于点x,x的左右子树中的任意一棵的大小大于了x子树大小乘以α,说明原树已经非常不平衡了,需要将其还原成一个点的序列(这一过程被称为拍扁),然后重建一次.当然,你也可以根据你的心情对α值做调整.
询问操作的本质是搜索+用估价函数剪枝（估价函数的结果一定比实际最优解小），先搜索更优的，用更优的那个子树更新答案；判断次优的子树的估价函数是否小于当前答案，可以发现这个概率是比较小的，进入次优子树搜索的概率就小一些。
时间复杂度？我不知道，反正现在没人会来卡。
#define ratio 0.75
co int N=1e6+1,INF=0x3f3f3f3f;
struct point{int x[2];}p[N];
struct node{int mi[2],mx[2],ls,rs,sz;point tp;}tr[N];
int n,m,rt,cur,top,WD,ans,rub[N];
int operator<(co point&a,co point&b){
return a.x[WD]<b.x[WD];
}
int newnode(){
return top?rub[top--]:++cur;
}
void up(int k){
int l=tr[k].ls,r=tr[k].rs;
for(int i=0;i<2;++i){
tr[k].mi[i]=tr[k].mx[i]=tr[k].tp.x[i];
if(l) tr[k].mi[i]=min(tr[k].mi[i],tr[l].mi[i]),tr[k].mx[i]=max(tr[k].mx[i],tr[l].mx[i]);
if(r) tr[k].mi[i]=min(tr[k].mi[i],tr[r].mi[i]),tr[k].mx[i]=max(tr[k].mx[i],tr[r].mx[i]);
}
tr[k].sz=tr[l].sz+tr[r].sz+1;
}
int build(int l,int r,int wd){
if(l>r) return 0;
int k=newnode(),mid=(l+r)>>1;
WD=wd,nth_element(p+l,p+mid,p+r+1),tr[k].tp=p[mid];
tr[k].ls=build(l,mid-1,wd^1),tr[k].rs=build(mid+1,r,wd^1);
up(k);return k;
}
void pia(int k,int num){
if(tr[k].ls) pia(tr[k].ls,num);
p[num+tr[tr[k].ls].sz+1]=tr[k].tp,rub[++top]=k;
if(tr[k].rs) pia(tr[k].rs,num+tr[tr[k].ls].sz+1);
}
void check(int&k,int wd){
if(ratio*tr[k].sz<tr[tr[k].ls].sz||ratio*tr[k].sz<tr[tr[k].rs].sz)
pia(k,0),k=build(1,tr[k].sz,wd);
}
void ins(co point&tmp,int&k,int wd){
if(!k) {k=newnode(),tr[k].tp=tmp,tr[k].ls=tr[k].rs=0,up(k);return;}
if(tr[k].tp.x[wd]<tmp.x[wd]) ins(tmp,tr[k].rs,wd^1);
else ins(tmp,tr[k].ls,wd^1);
up(k),check(k,wd);
}
int getdis(co point&tmp,int k){
int re=0;
for(int i=0;i<2;++i)
re+=max(0,tmp.x[i]-tr[k].mx[i])+max(0,tr[k].mi[i]-tmp.x[i]);
return re;
}
int dist(co point&a,co point&b) {return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);}
void query(co point&tmp,int k){
ans=min(ans,dist(tmp,tr[k].tp));
int dl=INF,dr=INF;
if(tr[k].ls) dl=getdis(tmp,tr[k].ls);
if(tr[k].rs) dr=getdis(tmp,tr[k].rs);
if(dl<dr){
if(dl<ans) query(tmp,tr[k].ls);
if(dr<ans) query(tmp,tr[k].rs);
}
else{
if(dr<ans) query(tmp,tr[k].rs);
if(dl<ans) query(tmp,tr[k].ls);
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int bj;
read(n),read(m);
for(int i=1;i<=n;++i) read(p[i].x[0]),read(p[i].x[1]);
rt=build(1,n,0);
while(m--){
point tmp;
read(bj),read(tmp.x[0]),read(tmp.x[1]);
if(bj==1) ins(tmp,rt,0);
else ans=INF,query(tmp,rt),printf("%d\n",ans);
}
return 0;
}
The Closest M Points
软工学院的课程很讨厌！ZLC同志遇到了一个头疼的问题：在K维空间里面有许多的点，对于某些给定的点，ZLC需要找到和它最近的m个点。
（这里的距离指的是欧几里得距离：D(p, q) = D(q, p) = sqrt((q1 - p1)2 + (q2 - p2)2 + (q3 - p3)2 + … + (qn - pn)2)
ZLC要去打Dota，所以就麻烦你帮忙解决一下了……
点数n(1 <= n <= 50000)，和维度数k(1 <= k <= 5)。
询问数量t(1 <= t <= 10000)
查询最近的m个点(1 <= m <= 10)
Regina8023的题解
此题要求前k小答案，我们首先把k个inf加入大根堆，每次判断是否比堆顶小来确定是否要加入答案。
不分析时间复杂度，这种做法据说可以卡掉。
co int N=5e4+1,INF=0x3f3f3f3f;
priority_queue<pii> pq;
int q[5],ans[11];
struct node{
int ma[5],mi[5],d[5],l,r;
}t[N];
int root,n,m,k,now;
bool cmp(co node&a,co node&b){
return a.d[now]<b.d[now];
}
void update(int x){
int l=t[x].l,r=t[x].r;
for(int i=0;i<k;++i){
t[x].mi[i]=min(t[x].mi[i],min(t[l].mi[i],t[r].mi[i]));
t[x].ma[i]=max(t[x].ma[i],max(t[l].ma[i],t[r].ma[i]));
}
}
int build(int l,int r,int d){
now=d;
int mid=(l+r)>>1;
nth_element(t+l,t+mid,t+r+1,cmp);
t[mid].l=l<mid?build(l,mid-1,(d+1)%k):0;
t[mid].r=mid<r?build(mid+1,r,(d+1)%k):0;
update(mid);
return mid;
}
int sqr(int x){
return x*x;
}
int dis(int x){
int re=0;
for(int i=0;i<k;++i)
re+=sqr(t[x].d[i]-q[i]);
return re;
}
int get(int x){
int re=0;
for(int i=0;i<k;++i){
if(q[i]<t[x].mi[i]) re+=sqr(t[x].mi[i]-q[i]);
if(q[i]>t[x].ma[i]) re+=sqr(q[i]-t[x].ma[i]);
}
return re;
}
void query(int x){
if(!x) return;
int d0=dis(x),dl=get(t[x].l),dr=get(t[x].r);
if(d0<pq.top().first) pq.pop(),pq.push(pii(d0,x));
if(dl<dr){
if(dl<pq.top().first) query(t[x].l);
if(dr<pq.top().first) query(t[x].r);
}
else{
if(dr<pq.top().first) query(t[x].r);
if(dl<pq.top().first) query(t[x].l);
}
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
while(~scanf("%d%d",&n,&k)){
for(int i=0;i<k;++i)
t[0].ma[i]=-INF,t[0].mi[i]=INF;
for(int i=1;i<=n;++i)
for(int j=0;j<k;++j)
t[i].ma[j]=t[i].mi[j]=read(t[i].d[j]);
root=build(1,n,0);
int Q=read<int>();
while(Q--){
for(int i=0;i<k;++i)
read(q[i]);
read(m);
for(int i=1;i<=m;++i)
pq.push(pii(INF,0));
query(root);
for(int i=1;i<=m;++i)
ans[i]=pq.top().second,pq.pop();
printf("the closest %d points are:\n",m);
for(int i=m;i;--i){
for(int j=0;j<k;++j){
if(j) putchar(' ');
printf("%d",t[ans[i]].d[j]);
}
puts("");
}
}
}
return 0;
}