P4169 [Violet]天使玩偶/SJY摆棋子

题目背景

感谢@浮尘ii 提供的一组hack数据

题目描述

Ayu 在七年前曾经收到过一个天使玩偶,当时她把它当作时间囊埋在了地下。而七年后 的今天,Ayu 却忘了她把天使玩偶埋在了哪里,所以她决定仅凭一点模糊的记忆来寻找它。

我们把 Ayu 生活的小镇看作一个二维平面坐标系,而 Ayu 会不定时地记起可能在某个点 (xmy) 埋下了天使玩偶;或者 Ayu 会询问你,假如她在 (x,y) ,那么她离近的天使玩偶可能埋下的地方有多远。

因为 Ayu 只会沿着平行坐标轴的方向来行动,所以在这个问题里我们定义两个点之间的距离为dist(A,B)=|Ax-Bx|+|Ay-By|。其中 Ax 表示点 A的横坐标,其余类似。

输入输出格式

输入格式:

第一行包含两个整数n和m ,在刚开始时,Ayu 已经知道有n个点可能埋着天使玩偶, 接下来 Ayu 要进行m 次操作

接下来n行,每行两个非负整数 (xi,yi),表示初始n个点的坐标。

再接下来m 行,每行三个非负整数 t,xi,yi。

如果t=1 ,则表示 Ayu 又回忆起了一个可能埋着玩偶的点 (xi,yi) 。

如果t=2 ,则表示 Ayu 询问如果她在点 (xi,yi) ,那么在已经回忆出来的点里,离她近的那个点有多远

输出格式:

对于每个t=2 的询问,在单独的一行内输出该询问的结果。

输入输出样例

输入样例#1:
2 3
1 1
2 3
2 1 2
1 3 3
2 4 2
输出样例#1:
1
2

说明

n,m<=300 000

xi,yi<=1 000 000

Solution:
  本题巨说是点分治裸题。。。然而我用$kd-tree$水了波$90$。(应该是可以$A$的,但是暂时不会玄学转树,留坑待填~)

  有必要先解释一下变量含义:$(d[0],d[1])$为当前根节点的坐标,$(mn[0],mn[1])$表示当前节点代表的二维平面中最左下角的坐标,$(mx[0],mx[1])$表示最右上角的坐标,$l,r$分别表示当前节点的左、右儿子。

  思路比较简单,构建二维搜索树,将每个点拍到面上去,从根节点往下每层交替按$x$和$y$为关键字建树。

  建树过程,要尽可能使得树保持平衡,所以每次以区间中间为当前根节点建树,二维平面分为左部和右部两部分,分别表示当前节点的左儿子和右儿子。

代码:

#include<bits/stdc++.h>
#define il inline
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define Min(a,b) ((a)>(b)?(b):(a))
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
const int N=,inf=;
int n,m,x,y,opt,ans,cmpd,root;
struct node{
int d[],l,r,mn[],mx[];
bool operator <(const node a){
return ((d[cmpd]<a.d[cmpd])||(d[cmpd]==a.d[cmpd]&&d[!cmpd]<a.d[!cmpd]));
}
}t[N]; il int gi(){
int a=;char x=getchar();bool f=;
while((x<''||x>'')&&x!='-')x=getchar();
if(x=='-')x=getchar(),f=;
while(x>=''&&x<='')a=(a<<)+(a<<)+x-,x=getchar();
return f?-a:a;
} il void update(int rt){
int ls=t[rt].l,rs=t[rt].r;
if(ls){
t[rt].mn[]=Min(t[rt].mn[],t[ls].mn[]);
t[rt].mn[]=Min(t[rt].mn[],t[ls].mn[]);
t[rt].mx[]=Max(t[rt].mx[],t[ls].mx[]);
t[rt].mx[]=Max(t[rt].mx[],t[ls].mx[]);
}
if(rs){
t[rt].mn[]=Min(t[rt].mn[],t[rs].mn[]);
t[rt].mn[]=Min(t[rt].mn[],t[rs].mn[]);
t[rt].mx[]=Max(t[rt].mx[],t[rs].mx[]);
t[rt].mx[]=Max(t[rt].mx[],t[rs].mx[]);
}
} il int build(int l,int r,int tw){
cmpd=tw;
int mid=l+r>>;
nth_element(t+l+,t+mid+,t+r+);
t[mid].mn[]=t[mid].mx[]=t[mid].d[];
t[mid].mn[]=t[mid].mx[]=t[mid].d[];
if(l!=mid)t[mid].l=build(l,mid-,!tw);
if(r!=mid)t[mid].r=build(mid+,r,!tw);
update(mid);
return mid;
} il void insert(int rt){
int op=,p=root;
while(){
if(t[rt].mn[]<t[p].mn[])t[p].mn[]=t[rt].mn[];
if(t[rt].mn[]<t[p].mn[])t[p].mn[]=t[rt].mn[];
if(t[rt].mx[]>t[p].mx[])t[p].mx[]=t[rt].mx[];
if(t[rt].mx[]>t[p].mx[])t[p].mx[]=t[rt].mx[];
if(t[rt].d[op]>=t[p].d[op]){
if(!t[p].r){t[p].r=rt;return;}
else p=t[p].r;
}
else {
if(!t[p].l){t[p].l=rt;return;}
else p=t[p].l;
}
op=!op;
}
} il int mhd(int rt,int x,int y){
int s=;
if(x<t[rt].mn[])s+=(t[rt].mn[]-x);
if(x>t[rt].mx[])s+=(x-t[rt].mx[]);
if(y<t[rt].mn[])s+=(t[rt].mn[]-y);
if(y>t[rt].mx[])s+=(y-t[rt].mx[]);
return s;
} il void query(int rt){
int d0,dl,dr;
d0=abs(t[rt].d[]-x)+abs(t[rt].d[]-y);
if(d0<ans)ans=d0;
if(t[rt].l)dl=mhd(t[rt].l,x,y);
else dl=inf;
if(t[rt].r)dr=mhd(t[rt].r,x,y);
else dr=inf;
if(dl<dr){
if(dl<ans)query(t[rt].l);
if(dr<ans)query(t[rt].r);
}
else {
if(dr<ans)query(t[rt].r);
if(dl<ans)query(t[rt].l);
}
} int main(){
n=gi(),m=gi();
For(i,,n) t[i].d[]=gi(),t[i].d[]=gi();
root=build(,n,);
while(m--){
opt=gi(),x=gi(),y=gi();
if(opt==){
n++;
t[n].mn[]=t[n].mx[]=t[n].d[]=x;
t[n].mn[]=t[n].mx[]=t[n].d[]=y;
insert(n);
}
else {
ans=inf;
query(root);
printf("%d\n",ans);
}
}
return ;
}
上一篇:洛谷P4169 [Violet]天使玩偶/SJY摆棋子(CDQ分治)


下一篇:洛谷P4169 [Violet]天使玩偶/SJY摆棋子