Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 3128 Solved: 1067
Description
这天，SJY显得无聊。在家自己玩。在一个棋盘上，有N个黑色棋子。他每次要么放到棋盘上一个黑色棋子，要么放上一个白色棋子，如果是白色棋子，他会找出距离这个白色棋子最近的黑色棋子。此处的距离是 曼哈顿距离 即(|x1-x2|+|y1-y2|) 。现在给出N<=500000个初始棋子。和M<=500000个操作。对于每个白色棋子，输出距离这个白色棋子最近的黑色棋子的距离。同一个格子可能有多个棋子。
Input
第一行两个数 N M
以后M行，每行3个数 t x y
如果t=1 那么放下一个黑色棋子
如果t=2 那么放下一个白色棋子
Output
对于每个T=2 输出一个最小距离
Sample Input
2 3
1 1
2 3
2 1 2
1 3 3
2 4 2
1 1
2 3
2 1 2
1 3 3
2 4 2
Sample Output
1
2
2
HINT
kdtree可以过
Source
K-Dtree模板题
似乎有种懂了的错觉
(錯覚？それでは、聞いてください....)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int INF=1e9;
const int mxn=;
int read(){
int x=,f=;char ch=getchar();
while(ch<'' || ch>''){if(ch=='-')f=-;ch=getchar();}
while(ch>='' && ch<=''){x=x*-''+ch;ch=getchar();}
return x*f;
}
int nowD;
struct node{
int min[],max[];
int d[];
int l,r;
}t[mxn<<];
int root,nct=;
int cmp(const node a,const node b){
if(a.d[nowD]==b.d[nowD])return a.d[nowD^]<b.d[nowD^];
return a.d[nowD]<b.d[nowD];
}
int qx,qy;//查询参数
void pushup(int rt,int c){//更新结点信息
t[rt].max[]=max(t[rt].max[],t[c].max[]);
t[rt].min[]=min(t[rt].min[],t[c].min[]);
t[rt].max[]=max(t[rt].max[],t[c].max[]);
t[rt].min[]=min(t[rt].min[],t[c].min[]);
return;
}
int Build(int l,int r,int D){
nowD=D;int mid=(l+r)>>;
nth_element(t+l,t+mid,t+r+,cmp);
t[mid].max[]=t[mid].min[]=t[mid].d[];
t[mid].max[]=t[mid].min[]=t[mid].d[];
if(l!=mid) t[mid].l=Build(l,mid-,D^);
if(r!=mid) t[mid].r=Build(mid+,r,D^);
if(t[mid].l)pushup(mid,t[mid].l);
if(t[mid].r)pushup(mid,t[mid].r);
return mid;
}
void insert(int x){//插入新结点
int now=root,D=;
while(){
pushup(now,x);
if(t[x].d[D]>=t[now].d[D]){
if(!t[now].r){t[now].r=x;return;}
else now=t[now].r;
}
else{
if(!t[now].l){t[now].l=x;return;}
else now=t[now].l;
}
D^=;
}
return;
}
int Dist(int k){//估价
int res=;
if(qx<t[k].min[])res+=t[k].min[]-qx;
if(qx>t[k].max[])res+=qx-t[k].max[];
if(qy<t[k].min[])res+=t[k].min[]-qy;
if(qy>t[k].max[])res+=qy-t[k].max[];
return res;
}
int ans;
void query(int rt){
int dx,dy,tmp;
// printf("rt:%d pos:%d %d ans:%d\n",rt,t[rt].d[0],t[rt].d[1],ans);
tmp=abs(t[rt].d[]-qx)+abs(t[rt].d[]-qy);
if(tmp<ans)ans=tmp;
if(t[rt].l) dx=Dist(t[rt].l);else dx=INF;
if(t[rt].r) dy=Dist(t[rt].r);else dy=INF;
if(dx<dy){
if(dx<ans) query(t[rt].l);
if(dy<ans) query(t[rt].r);
}
else{
if(dy<ans) query(t[rt].r);
if(dx<ans) query(t[rt].l);
}
return;
}
int n,m;
int main(){
int i,j;
n=read();m=read();
int T,x,y;
for(i=;i<=n;i++){
t[++nct].d[]=read();
t[nct].d[]=read();
}
root=Build(,n,);
while(m--){
T=read();x=read();y=read();
if(T==){
t[++nct].d[]=x; t[nct].d[]=y;
t[nct].max[]=t[nct].min[]=t[nct].d[];
t[nct].max[]=t[nct].min[]=t[nct].d[];
insert(nct);
}
else{
qx=x;qy=y;ans=INF;
query(root);
printf("%d\n",ans);
}
}
return ;
}