板子题，但这题很神奇的是加了一个优化以后直接从11292ms跑成了1548ms(即代码中替换掉注释部分的内容)
优化具体原理应该是先将maxans/minans尽量放大/减小
这题求的是每个点到其他点的最长路径和最短路径，符合kd-tree的应用范围，那么优化的暴力就来了
这里的mindis尤其要注意，一开始写错了都没发现
#include<cstdio> #include<cctype> #include<cmath> #include<algorithm> #define maxn 500002 using namespace std; int n,m,cmpd,rt,maxans,minans; struct data{ int x[2],mn[2],mx[2],l,r; friend bool operator<(data a,data b){return a.x[cmpd]<b.x[cmpd];} friend int dis(data a,data b){return abs(a.x[0]-b.x[0])+abs(a.x[1]-b.x[1]);} friend int maxdis(data a,data b){return max(abs(a.x[1]-b.mn[1]),abs(a.x[1]-b.mx[1]))+max(abs(a.x[0]-b.mn[0]),abs(a.x[0]-b.mx[0]));} friend int mindis(data a,data b){ int s=0;for(int i=0;i<=1;i++)s+=max(a.x[i]-b.mx[i],0),s+=max(b.mn[i]-a.x[i],0); return s; }//这里的mindis其实没什么用，刚开始还写错了 }tr[maxn]; void read(int &x){ char ch=getchar();x=0;int f=1; while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();} while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} x*=f; } void updata(int x){ int ls=tr[x].l,rs=tr[x].r; if(ls>0){ if(tr[ls].mn[0]<tr[x].mn[0])tr[x].mn[0]=tr[ls].mn[0]; if(tr[ls].mn[1]<tr[x].mn[1])tr[x].mn[1]=tr[ls].mn[1]; if(tr[ls].mx[0]>tr[x].mx[0])tr[x].mx[0]=tr[ls].mx[0]; if(tr[ls].mx[1]>tr[x].mx[1])tr[x].mx[1]=tr[ls].mx[1]; } if(rs>0){ if(tr[rs].mn[0]<tr[x].mn[0])tr[x].mn[0]=tr[rs].mn[0]; if(tr[rs].mn[1]<tr[x].mn[1])tr[x].mn[1]=tr[rs].mn[1]; if(tr[rs].mx[0]>tr[x].mx[0])tr[x].mx[0]=tr[rs].mx[0]; if(tr[rs].mx[1]>tr[x].mx[1])tr[x].mx[1]=tr[rs].mx[1]; } } int buildtr(int l,int r,int flag){ cmpd=flag; int mid=(l+r)>>1; nth_element(tr+l,tr+mid,tr+r+1); tr[mid].l=tr[mid].r=0; tr[mid].mn[0]=tr[mid].mx[0]=tr[mid].x[0]; tr[mid].mn[1]=tr[mid].mx[1]=tr[mid].x[1]; if(l<mid)tr[mid].l=buildtr(l,mid-1,!flag); if(r>mid)tr[mid].r=buildtr(mid+1,r,!flag); updata(mid); return mid; } void getmx(int whic,int x){ if(!x)return; maxans=max(maxans,dis(tr[whic],tr[x])); int ls=tr[x].l,rs=tr[x].r,ldis=-1e9,rdis=-1e9; /* if(ls>0 && ldis>maxans)getmx(whic,ls); if(rs>0 && rdis>maxans)getmx(whic,rs);*/ if (ls)ldis=maxdis(tr[whic],tr[ls]);if(rs)rdis=maxdis(tr[whic],tr[rs]); if (ldis>rdis){if(ldis>maxans) getmx(whic,ls);if(rdis>maxans) getmx(whic,rs);} else { if (rdis>maxans) getmx(whic,rs); if (ldis>maxans) getmx(whic,ls); } } void getmn(int whic,int x){ if(!x)return; if(whic!=x)minans=min(minans,dis(tr[whic],tr[x])); int ldis=1e9,rdis=1e9,ls=tr[x].l,rs=tr[x].r; if (ls) ldis=mindis(tr[whic],tr[ls]); if (rs) rdis=mindis(tr[whic],tr[rs]); /*if(ls>0 && ldis<minans)getmn(whic,ls); if(rs>0 && rdis<minans)getmn(whic,rs);*/ if (ldis<rdis){if(ldis<minans)getmn(whic,ls);if(rdis<minans)getmn(whic,rs); } else {if(rdis<minans)getmn(whic,rs);if(ldis<minans)getmn(whic,ls);} } int query(){ int res=2e9; for(int i=1;i<=n;i++){ maxans=-1e9;minans=1e9; getmx(i,rt); getmn(i,rt); res=min(res,maxans-minans); } return res; } int main(){ read(n); for(int i=1;i<=n;i++)read(tr[i].x[0]),read(tr[i].x[1]); rt=buildtr(1,n,0); printf("%d\n",query()); }