P4169 [Violet]天使玩偶/SJY摆棋子
链接
思路
luogu以前用CDQ一直过不去。
bzoj还是卡时过去的。
今天终于用k-dtree给过了。
代码
#include <bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f,N=1e6+7;;
const double alph(0.75);
int WD,ans,rub[N],tot,top;
struct Point {
int x[2];
bool operator < (const Point b) const {
return x[WD]<b.x[WD];
}
}p[N];
struct node {
int mi[2],ma[2],ls,rs,siz;
Point tp;
}e[N];
int newnode() {
if(top) return rub[top--];
return ++tot;
}
void up(int u) {
for(int i=0;i<2;++i) {
e[u].mi[i]=e[u].ma[i]=e[u].tp.x[i];
if(e[u].ls) {
e[u].mi[i]=min(e[u].mi[i],e[e[u].ls].mi[i]);
e[u].ma[i]=max(e[u].ma[i],e[e[u].ls].ma[i]);
}
if(e[u].rs) {
e[u].mi[i]=min(e[u].mi[i],e[e[u].rs].mi[i]);
e[u].ma[i]=max(e[u].ma[i],e[e[u].rs].ma[i]);
}
}
e[u].siz=e[e[u].ls].siz+e[e[u].rs].siz+1;
}
int build(int l,int r,int wd) {
if(l>r) return 0;
int u=newnode(),mid=(l+r)>>1;
WD=wd;
nth_element(p+l,p+mid,p+r+1);
e[u].tp=p[mid];
e[u].ls=build(l,mid-1,wd^1);
e[u].rs=build(mid+1,r,wd^1);
up(u);
return u;
}
void pia(int u,int num) {
if(e[u].ls) pia(e[u].ls,num);
p[num+e[e[u].ls].siz+1]=e[u].tp;
rub[++top]=u;
if(e[u].rs) pia(e[u].rs,num+e[e[u].ls].siz+1);
}
void check(int &u,int wd) {
if(alph*e[u].siz<e[e[u].ls].siz||alph*e[u].siz<e[e[u].rs].siz)
pia(u,0),u=build(1,e[u].siz,wd);
}
void insert(Point tmp,int &u,int wd) {
if(!u) {u=newnode(),e[u].tp=tmp;e[u].ls=e[u].rs=0;up(u);return;}
if(e[u].tp.x[wd]<tmp.x[wd]) insert(tmp,e[u].rs,wd^1);
else insert(tmp,e[u].ls,wd^1);
up(u),check(u,wd);
}
int getdis(Point tmp,int u) {
int res=0;
for(int i=0;i<=1;++i)
res+=max(0,e[u].mi[i]-tmp.x[i])+max(0,tmp.x[i]-e[u].ma[i]);
return res;
}
int dis(Point a,Point b) {
return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);
}
void query(Point tmp,int u) {
ans=min(ans,dis(e[u].tp,tmp));
int dl=INF,dr=INF;
if(e[u].ls) dl=getdis(tmp,e[u].ls);
if(e[u].rs) dr=getdis(tmp,e[u].rs);
if(dl<dr) {
if(dl<ans) query(tmp,e[u].ls);
if(dr<ans) query(tmp,e[u].rs);
} else {
if(dr<ans) query(tmp,e[u].rs);
if(dl<ans) query(tmp,e[u].ls);
}
}
int main() {
int opt,n,m,rt;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) scanf("%d%d",&p[i].x[0],&p[i].x[1]);
rt=build(1,n,0);
while(m--) {
Point tmp;
scanf("%d%d%d",&opt,&tmp.x[0],&tmp.x[1]);
if(opt==1) insert(tmp,rt,0);
else ans=INF,query(tmp,rt),printf("%d\n",ans);
}
return 0;
}