天使玩偶
题目链接：[https://www.luogu.com.cn/problem/P4169]
快捷版题意：
平面上给n个点，有一下两种操作：
- 新加一个点
给出一个点，询问这个点到所有已加入点的距离最小值（距离定义为曼哈顿距离）
思路：
设给出点为P
曼哈顿距离：\(dis(A,P)=|xa-xp|+|ya-yp|\)
绝对值太讨厌了！拆开！
不妨设A点在P点左下方
所以\(dis(A,P)=(xa+ya)-(xp+yp)\)
\((xa+ya)\)为定值，因此需要最大化\((xp+yp)\)，同时满足\(xa>=xp,ya>=yp\)
发现这就是一个变式的三维偏序，于是上cdq分治即可
但A点不一定在P点左下方呀
没关系，我们可以将坐标系进行上下翻折，左右翻折
具体来说，就是先求出横纵坐标的最大值ex
将一个点\((x,y)\)进行如此变换：
\((x,y)->(ex-x,y)\)
\((x,y)->(x,ex-y)\)
\((x,y)->(ex-x,ex-y)\)
然后再类似地做一遍cdq分治就好了注意事项：
此题不仅坑多，还要卡常，可谓是毒瘤- 数组要开大（玄学，我也不知道为什么）
- 树状数组中各种坐标到要把0给避开，否则死循环
- 当询问无解时，千万不能返回0，要返回负无穷
......
code
#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5;
int n,m,ex;
struct node{int x,y,tp,id,ans;}a[N],b[N],tmp[N];
inline char nc()
{
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
char ch=nc();int sum=0;
while(!(ch>='0'&&ch<='9'))ch=nc();
while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
return sum;
}
struct tree{
int c[N];
inline int lowbit(int x){return x&(-x);}
inline void add(int x,int y)
{
for(;x<ex;x+=lowbit(x)) c[x]=max(c[x],y);
}
inline int query(int x)
{
int ans=0;
for(;x;x-=lowbit(x)) ans=max(ans,c[x]);
return ans?ans:-1e9;//坑啊
}
inline void clean(int x)
{
for(;c[x];x+=lowbit(x))c[x]=0;
}
}T;
void cdq(int l,int r)
{
if(l==r) return;
int mid=l+r>>1;
cdq(l,mid);cdq(mid+1,r);
int i=l,j=mid+1,k=l;
while(j<=r)
{
while(i<=mid&&b[i].x<=b[j].x)
{
if(b[i].tp==1) T.add(b[i].y,b[i].x+b[i].y);
tmp[k++]=b[i++];
}
if(b[j].tp==2)
a[b[j].id].ans=min(a[b[j].id].ans,b[j].x+b[j].y-T.query(b[j].y));
tmp[k++]=b[j++];
}
for(int e=l;e<i;++e)
if(b[e].tp==1) T.clean(b[e].y);
for(int e=i;e<=mid;++e)tmp[k++]=b[e];
for(int e=l;e<=r;++e) b[e]=tmp[e];
}
inline void work(bool sx,bool sy)
{
for(int i=1;i<=n+m;++i)
{
b[i]=a[i];
if(sx) b[i].x=ex-b[i].x;
if(sy) b[i].y=ex-b[i].y;
}
cdq(1,n+m);
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
{
a[i].x=read()+1;a[i].y=read()+1;
a[i].tp=1;a[i].id=i;
ex=max(ex,max(a[i].x,a[i].y));
}
for(int i=n+1;i<=n+m;++i)
{
a[i].tp=read();a[i].id=i;
a[i].x=read()+1,a[i].y=read()+1;
a[i].ans=1e9;
ex=max(ex,max(a[i].x,a[i].y));
}
++ex;
work(0,0),work(1,0),work(0,1),work(1,1);
for(int i=n+1;i<=n+m;++i)
if(a[i].tp==2) printf("%d\n",a[i].ans);
return 0;
}1、Cable master（好题，二分）
2、好文章有多好
3、Tomcat 安装配置
4、python学习笔记
5、开发人员有用的几个网站