题目大意

给你一个有\(n\)个点的平面。

选择三个点，求两两之间曼哈顿距离和的最大值和最小值。

---

思考历程&正解

比赛的时候没有想太多，但感觉似乎比较水……

首先有个很显然的性质，答案为这三个点的最大最小横坐标之差和最大最小纵坐标之差的和。

可以把它看成矩形的周长，容易发现矩形至少一个顶点是三个点之一。

后来才发现水的是求最大值，而不是求最小值。

比赛之后开始和WMY刚……

最大值是很好求的。我一开始打了个线段树来求，后来发现根本不用……

求出所有点的\(Xmin,Xmax,Ymin,Ymax\)，然后\(O(n)\)扫一遍，贪心一下就没了。

主要的问题在于最小值。

显然有两种情况：三个点都在矩形边上；有一个点在矩形内部。

第二种情况很好求，枚举中间的点，线段树维护右上和左下（或右下和左上）的最近的点。

主要问题是第一种情况。

假设我们现在已经将点按照\(x\)坐标为第一关键字排序，以\(y\)坐标为第二关键字排序，都是从小到大。

枚举矩形左下的节点（至于其它方向的节点，直接旋转或对称就行了）。

（很简陋的一张图）

左下的节点（记作\(A\)）固定了\(Xmin\)和\(Ymin\)，右边的节点（记作\(B\)）固定了\(Xmax\)，上边的节点（记作\(C\)）固定了\(Ymax\)

由于\(A\)是固定的，所以我们值只需要让\(Xmax+Ymax\)最小。

考虑平行于\(y\)轴的扫描线，从右到左。

我们需要将\(B\)点表示的\(Xmax\)挂在\(C\)点上，计算\(A\)点答案的时候要查询到\(C\)点。

维护最小的\(Ymax+Xmax\)，挂在行上。

扫描线扫到\(C\)的时候，就将\(C.y\)这一行的\(Xmax\)更新一下。

扫描线扫到\(B\)的时候，就将\([0,B.y)\)的\(Ymax\)更新一下。

扫描线扫到\(A\)的时候，是询问\([A.y,10^8]\)的最小\(Xmax+Ymax\)

（在实际操作的时候，每个点都需要进行三个操作，因为它有可能是\(A\)点、\(B\)点、\(C\)点）

接下来考虑如何维护这个东西。

线段树上每个节点维护\(ans\)、\(MIN_{Xmax}、tag\)

既然\(Ymax\)是区间修改，肯定是要打\(tag\)标记的。

在打\(tag\)标记的时候（以及下传的时候），若\(MIN_{Xmax}+tag<ans\)，则更新\(ans\)

若这个点原先就有个\(tag\)，就跟这个\(tag\)比较大小，若更小，则替代它。

对于\(Xmax\)的单点修改，直接在线段树中找到对应的点（找的时候标记要下传，到了最底端的时候标记清空，这就使得这个节点及它的祖先都没有标记），修改它的\(MIN_{Xmax}\)（但是\(ans\)是不用改的，因为\(Ymax\)是在\(Xmax\)后面出现的，现在这个新的\(Xmax\)暂时是最后一个，没有匹配的\(Ymax\)）

然后这道题就被解决了。

---

代码

using namespace std;#include 
    
     #include 
     
      #include 
      
       #define N 100010#define MAX 100000000#define INF 1000000000int n;struct DOT{    int x,y;    int num;} d[N];inline void rever(int a,int b){//把所有点进行对称操作    for (int i=1;i<=n;++i)        d[i]={a==1?d[i].x:MAX-d[i].x,b==1?d[i].y:MAX-d[i].y,d[i].num};}inline bool cmpd(const DOT &a,const DOT &b){    return a.x
       
        val=max(t->val,c);        return;    }    int mid=l+r>>1;    if (x<=mid)        change1(t->lc==null1?t->lc=newnode1():t->lc,l,mid,x,c);    else        change1(t->rc==null1?t->rc=newnode1():t->rc,mid+1,r,x,c);    t->val=max(t->lc->val,t->rc->val);}int query1(Node1 *t,int l,int r,int st,int en){    if (t==null1)        return -INF;    if (st<=l && r<=en)        return t->val;    int mid=l+r>>1,res=-INF;    if (st<=mid)        res=max(res,query1(t->lc,l,mid,st,en));    if (mid
        
         rc,mid+1,r,st,en));    return res;}struct Node2 *null2;struct Node2{    Node2 *lc,*rc;    int ans,minx,tag;    inline void gmin(int y){        if (this==null2)            return;        if (y
         
          gmin(tag); rc->gmin(tag); tag=INF; } } inline void update(){ minx=min(lc->minx,rc->minx); ans=min(lc->ans,rc->ans); }} seg2[N*30],*root2;int cnt2;inline Node2 *newnode2(){return &(seg2[++cnt2]={null2,null2,INF,INF,INF});}void changex(Node2 *t,int l,int r,int x,int c){ if (l==r){ t->minx=c; t->tag=INF; return; } t->pushdown(); int mid=l+r>>1; if (x<=mid) changex(t->lc==null2?t->lc=newnode2():t->lc,l,mid,x,c); else changex(t->rc==null2?t->rc=newnode2():t->rc,mid+1,r,x,c); t->update();}void changey(Node2 *t,int l,int r,int st,int en,int c){ if (st<=l && r<=en){ t->gmin(c); return; } t->pushdown(); int mid=l+r>>1; if (st<=mid) changey(t->lc==null2?t->lc=newnode2():t->lc,l,mid,st,en,c); if (mid
          
           rc==null2?t->rc=newnode2():t->rc,mid+1,r,st,en,c); t->update();}int query2(Node2 *t,int l,int r,int st,int en){ if (t==null2) return INF; if (st<=l && r<=en) return t->ans; t->pushdown(); int mid=l+r>>1,res=INF; if (st<=mid) res=min(res,query2(t->lc,l,mid,st,en)); if (mid
           
            rc,mid+1,r,st,en)); return res;}int minxy[4][N];//用来记录某次状况下右上角的最近点inline void work(int flag){ sort(d+1,d+n+1,cmpd); if (flag<2){ //这是第二种情况的处理。不能在flag=2或3的时候处理一次，因为那时候不能保证顺序与这次完全相反 //如果顺序没有完全相反，两个点重合时候可能会当作三个点来看。 null1=seg1; *null1={null1,null1,-INF}; cnt1=0; root1=newnode1(); for (int i=1;i<=n;++i){ int tmp=query1(root1,0,MAX,0,d[i].y); minxy[flag][d[i].num]=min(d[i].x+d[i].y-tmp,INF); change1(root1,0,MAX,d[i].y,d[i].x+d[i].y); } null1=seg1; *null1={null1,null1,-INF}; cnt1=0; root1=newnode1(); for (int i=n;i>=1;--i){ int tmp=query1(root1,0,MAX,0,MAX-d[i].y); minxy[flag+2][d[i].num]=min(MAX-d[i].x+MAX-d[i].y-tmp,INF); change1(root1,0,MAX,MAX-d[i].y,MAX-d[i].x+MAX-d[i].y); } } null2=seg2; *null2={null2,null2,INF,INF,INF}; cnt2=0; root2=newnode2(); for (int i=n,j=n;i>=1;--i){ ans2=min(ans2,query2(root2,0,MAX,d[i].y,MAX)-d[i].x-d[i].y); if (d[i].y) changey(root2,0,MAX,0,d[i].y-1,d[i].y); changex(root2,0,MAX,d[i].y,d[i].x); }}int main(){// freopen("in.txt","r",stdin); scanf("%d",&n); int xmin=MAX,xmax=-MAX,ymin=MAX,ymax=-MAX; for (int i=1;i<=n;++i){ scanf("%d%d",&d[i].x,&d[i].y); d[i].num=i; xmin=min(xmin,d[i].x),xmax=max(xmax,d[i].x); ymin=min(ymin,d[i].y),ymax=max(ymax,d[i].y); } for (int i=1;i<=n;++i) ans1=max(ans1,max(d[i].x-xmin,xmax-d[i].x)+max(d[i].y-ymin,ymax-d[i].y)); work(0); rever(-1,1),work(1); rever(1,-1),work(2); rever(-1,1),work(3); for (int i=1;i<=n;++i) ans2=min(ans2,min(minxy[0][i]+minxy[2][i],minxy[1][i]+minxy[3][i])); printf("%d\n%d\n",ans1*2,ans2*2); return 0;}
           
          
         
        
       
      
     
    

好长啊……

实际上可以将第二种情况的线段树维护的最大值变成最小值，然后这两棵线段树就可以一起用了。

一起用的时候虽然会处理某些没有必要的东西，但是代码短啊……

---

总结

数据结构还是太菜了……