首先通過不斷翻轉坐標系，假設三個點以橫坐標為第一關鍵字，縱坐標為第二關鍵字排序后A在B前面，B在C前面。

那么只需要處理以下兩種情況：

?

1.B的縱坐標在AC之間，這時三個點的距離和為$2((x_C+y_C)-(x_A+y_A))$。

可以用線段樹處理出每個點作為B時$x_A+y_A$以及$x_C+y_C$的最值，然后更新答案即可。

?

2.B的縱坐標不超過A的縱坐標，這時三個點的距離和為$2((x_C+y_C)-x_A-y_B)$。

還是考慮枚舉B，需要維護它左邊每個A與右邊每個C合并的答案。

于是用一棵線段樹維護A集合，從n到1依次計算。

假設現在處理的是點B，那么先把B從A中刪除，然后查詢答案，再將B加入C集合中，也就是在A集合里進行區間更新。

?

時間復雜度$O(n\log n)$。

?

#include<cstdio> #include<algorithm> using namespace std; const int N=100010,M=262150,inf=1000000000; int n,i,ansmx,ansmn=inf,c[N],d[N],e[N],fmx[N],fmn[N]; struct P{int x,y;}a[N],b[N]; inline bool cmp(const P&a,const P&b){return a.x==b.x?a.y<b.y:a.x<b.x;} inline bool cmpb(const P&a,const P&b){return a.x<b.x;} inline void read(int&a){char c;while(!(((c=getchar())>='0')&&(c<='9')));a=c-'0';while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';} inline void umax(int&a,int b){if(a<b)a=b;} inline void umin(int&a,int b){if(a>b)a=b;} inline int findl(int x){int l=1,r=n,mid,t;while(l<=r)if(b[mid=(l+r)>>1].x>=x)r=(t=mid)-1;else l=mid+1;return t; } inline int findr(int x){int l=1,r=n,mid,t;while(l<=r)if(b[mid=(l+r)>>1].x<=x)l=(t=mid)+1;else r=mid-1;return t; } namespace Sub1{ struct Node{int mx,mn;}T[M]; void build(int x,int a,int b){T[x].mx=-inf,T[x].mn=inf;if(a==b)return;int mid=(a+b)>>1;build(x<<1,a,mid),build(x<<1|1,mid+1,b); } void ins(int x,int a,int b,int c,int p){umax(T[x].mx,p),umin(T[x].mn,p);if(a==b)return;int mid=(a+b)>>1;if(c<=mid)ins(x<<1,a,mid,c,p);else ins(x<<1|1,mid+1,b,c,p); } int askmx(int x,int a,int b,int c,int d){if(c<=a&&b<=d)return T[x].mx;int mid=(a+b)>>1,t=-inf;if(c<=mid)t=askmx(x<<1,a,mid,c,d);if(d>mid)umax(t,askmx(x<<1|1,mid+1,b,c,d));return t; } int askmn(int x,int a,int b,int c,int d){if(c<=a&&b<=d)return T[x].mn;int mid=(a+b)>>1,t=inf;if(c<=mid)t=askmn(x<<1,a,mid,c,d);if(d>mid)umin(t,askmn(x<<1|1,mid+1,b,c,d));return t; } } namespace Sub2{ struct Node{int mxx,mnx,mxv,mnv,mxt,mnt;}T[M]; inline void tagmx(int x,int p){umax(T[x].mxv,T[x].mxx+p);umax(T[x].mxt,p); } inline void tagmn(int x,int p){umin(T[x].mnv,T[x].mnx+p);umin(T[x].mnt,p); } inline void pb(int x){tagmx(x<<1,T[x].mxt);tagmx(x<<1|1,T[x].mxt);tagmn(x<<1,T[x].mnt);tagmn(x<<1|1,T[x].mnt);T[x].mxt=-inf,T[x].mnt=inf; } inline void up(int x){T[x].mxx=max(T[x<<1].mxx,T[x<<1|1].mxx);T[x].mnx=min(T[x<<1].mnx,T[x<<1|1].mnx);T[x].mxv=max(T[x<<1].mxv,T[x<<1|1].mxv);T[x].mnv=min(T[x<<1].mnv,T[x<<1|1].mnv); } void build(int x,int a,int b){T[x].mxt=-inf,T[x].mnt=inf;if(a==b){T[x].mxx=T[x].mnx=e[a];T[x].mxv=-inf,T[x].mnv=inf;return;}int mid=(a+b)>>1;build(x<<1,a,mid),build(x<<1|1,mid+1,b),up(x); } void del(int x,int a,int b,int c){if(a==b){T[x].mxx=T[x].mxv=-inf;T[x].mnx=T[x].mnv=inf;return;}pb(x);int mid=(a+b)>>1;if(c<=mid)del(x<<1,a,mid,c);else del(x<<1|1,mid+1,b,c);up(x); } void change(int x,int a,int b,int c,int d,int p){if(c<=a&&b<=d){tagmx(x,p);tagmn(x,p);return;}pb(x);int mid=(a+b)>>1;if(c<=mid)change(x<<1,a,mid,c,d,p);if(d>mid)change(x<<1|1,mid+1,b,c,d,p);up(x); } int askmx(int x,int a,int b,int c,int d){if(c<=a&&b<=d)return T[x].mxv;pb(x);int mid=(a+b)>>1,t=-inf;if(c<=mid)t=askmx(x<<1,a,mid,c,d);if(d>mid)umax(t,askmx(x<<1|1,mid+1,b,c,d));return up(x),t; } int askmn(int x,int a,int b,int c,int d){if(c<=a&&b<=d)return T[x].mnv;pb(x);int mid=(a+b)>>1,t=inf;if(c<=mid)t=askmn(x<<1,a,mid,c,d);if(d>mid)umin(t,askmn(x<<1|1,mid+1,b,c,d));return up(x),t; } } void solve(){for(sort(a+1,a+n+1,cmp),i=1;i<=n;i++)b[i].x=a[i].y,b[i].y=i;for(sort(b+1,b+n+1,cmpb),i=1;i<=n;i++)c[i]=findl(a[i].y),d[b[i].y]=i;for(i=1;i<=n;i++)e[d[i]]=-a[i].x;for(Sub1::build(1,1,n),i=1;i<=n;i++){fmx[i]=Sub1::askmx(1,1,n,1,c[i]);fmn[i]=Sub1::askmn(1,1,n,1,c[i]);Sub1::ins(1,1,n,c[i],-a[i].x-a[i].y);}for(Sub1::build(1,1,n),i=n;i;i--){umax(ansmx,Sub1::askmx(1,1,n,c[i],n)+fmx[i]);umin(ansmn,Sub1::askmn(1,1,n,c[i],n)+fmn[i]);Sub1::ins(1,1,n,c[i],a[i].x+a[i].y);}for(Sub2::build(1,1,n),i=n;i;i--){Sub2::del(1,1,n,d[i]);umax(ansmx,Sub2::askmx(1,1,n,c[i],n)-a[i].y);umin(ansmn,Sub2::askmn(1,1,n,c[i],n)-a[i].y);Sub2::change(1,1,n,1,findr(a[i].y),a[i].x+a[i].y);} } int main(){for(read(n),i=1;i<=n;i++)read(a[i].x),read(a[i].y);solve();for(i=1;i<=n;i++)a[i].x*=-1,a[i].y*=-1;solve();for(i=1;i<=n;i++)a[i].x*=-1;solve();for(i=1;i<=n;i++)a[i].x*=-1,a[i].y*=-1;solve();return printf("%d\n%d",ansmx*2,ansmn*2),0; }

　　

轉載于:https://www.cnblogs.com/clrs97/p/4872267.html

總結

以上是生活随笔為你收集整理的BZOJ2675 : Bomb的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。