題目鏈接

考慮對于兩個點a,b，距離為|x[a]-x[b]|+|y[a]-y[b]|，如果a在b的右上，那我們可以把絕對值去掉，即x[a]+y[a]-(x[b]+y[b])。
即我們要求滿足x[b]<=x[a]且y[b]<=y[a]的最大的x[b]+y[b]，用CDQ分治+樹狀數組解決。
那如果a不在b的右上呢？可以通過坐標變換解決(因為要求的只是相對距離)。
坐標變換可以用Xmax或Ymax減去xi或yi。
如果還用之前的方法，每次變換坐標前都要把操作序列變為初始序列(時間有序)，但是這樣很慢。。
不如在每次分治前按x sort一遍，分治中再以tm為關鍵字排序(同一區間內要時間有序)

優化: 遇到修改時才修改。所以先排好序再掃一遍更新答案

//43796kb 32744ms #include <cstdio> #include <cctype> #include <algorithm> //#define gc() getchar() #define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++) #define lb(x) (x)&-(x) const int N=5e5+5,MAXIN=2e6;int n,m,qcnt,acnt,Ans[N],A[N<<1]; char IN[MAXIN],*SS=IN,*TT=IN; struct Operation {int type,x,y,tm;Operation() {}Operation(int t,int _x,int _y,int _tm): type(t),x(_x),y(_y),tm(_tm) {}bool operator <(const Operation &a)const{return x==a.x?tm<a.tm:x<a.x;} }q[N<<1],tmp[N<<1];namespace BIT {int Max,t[1000005];void Update(int p,int v){while(p<=Max) t[p]=std::max(t[p],v),p+=lb(p);}int Query(int p){int res=0;while(p) res=std::max(t[p],res),p^=lb(p);//^代替- return res;}void Clear(int p){while(p<=Max)//被這個Max坑半晚上。。if(t[p]) t[p]=0,p+=lb(p);else break;} } inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } void CDQ(int l,int r) {if(l<r){int m=l+r>>1; int p1=l,p2=m+1,t=0,val;for(int i=l; i<=r; ++i)if(q[i].tm<=m) tmp[p1++]=q[i];else tmp[p2++]=q[i];for(int i=l; i<=r; ++i) q[i]=tmp[i];//先排好 這樣之后就可以只在查詢時更新了(不需要排序了) p1=l, p2=m+1;for(; p2<=r; ++p2)if(q[p2].type){for(; p1<=m&&q[p1].x<=q[p2].x; ++p1)if(!q[p1].type) A[++t]=q[p1].y,BIT::Update(q[p1].y,q[p1].x+q[p1].y);if(val=BIT::Query(q[p2].y))Ans[q[p2].type]=std::min(Ans[q[p2].type],q[p2].x+q[p2].y-val);//只在有點時更新答案! 否則答案會是它的x+y } // for(int i=l; i<p1; ++i) // if(!q[i].type) BIT::Clear(q[i].y);for(int i=1; i<=t; ++i) BIT::Clear(A[i]);CDQ(l,m), CDQ(m+1,r);} }int main() {n=read(),m=read();int Xmax=0,Ymax=0;for(int x,y,i=1; i<=n; ++i)//非負坐標...x=read()+1,y=read()+1,Xmax=std::max(Xmax,x),Ymax=std::max(Ymax,y),q[++qcnt]=Operation(0,x,y,qcnt);for(int t,x,y,i=1; i<=m; ++i)t=read(),x=read()+1,y=read()+1,Xmax=std::max(Xmax,x),Ymax=std::max(Ymax,y),q[++qcnt]=Operation(t==1?0:++acnt,x,y,qcnt);++Xmax,++Ymax,BIT::Max=Ymax;for(int i=1; i<=acnt; ++i) Ans[i]=Xmax+Ymax;std::sort(q+1,q+1+qcnt), CDQ(1,qcnt);for(int i=1; i<=qcnt; ++i) q[i].x=Xmax-q[i].x;std::sort(q+1,q+1+qcnt), CDQ(1,qcnt);for(int i=1; i<=qcnt; ++i) q[i].y=Ymax-q[i].y;std::sort(q+1,q+1+qcnt), CDQ(1,qcnt);for(int i=1; i<=qcnt; ++i) q[i].x=Xmax-q[i].x;std::sort(q+1,q+1+qcnt), CDQ(1,qcnt);for(int i=1; i<=acnt; ++i) printf("%d\n",Ans[i]);return 0; }

最初的代碼（肯定是會T）：

//懶得改了 看另一個吧。。 #include <cstdio> #include <cctype> #include <algorithm> #define gc() getchar() #define lb(x) (x)&-(x) const int N=3e5+5;int n,m,qcnt,acnt,Ans[N]; struct Operation {int type,x,y;Operation() {};Operation(int t,int _x,int _y): type(t),x(_x),y(_y) {};bool operator <(const Operation &a)const{return x==a.x?type<a.type:x<a.x;} }q[N<<1],tmp[N<<1],A[N<<1];namespace BIT {int Max,t[1000005];void Update(int p,int v){while(p<=Max) t[p]=std::max(t[p],v),p+=lb(p);}int Query(int p){int res=0;while(p) res=std::max(t[p],res),p-=lb(p);return res;}void Clear(int p){while(p<=Max)//被這個Max坑了半晚上。。if(t[p]) t[p]=0,p+=lb(p);else break;} } inline int read() {int now=0;register char c=gc();for(;!isdigit(c);c=gc());for(;isdigit(c);now=now*10+c-'0',c=gc());return now; } void CDQ(int l,int r) {//同理可以只在后半部分修改時更新前半部分 這個tm是有序的 結束后要按x歸并使x有序 if(l<r){int m=l+r>>1; CDQ(l,m), CDQ(m+1,r);int p1=l,p2=m+1,t=0,val;while(p1<=m&&p2<=r){if(q[p1]<q[p2]){if(!q[p1].type) BIT::Update(q[p1].y,q[p1].x+q[p1].y);tmp[t++]=q[p1++];}else{if(q[p2].type)if(val=BIT::Query(q[p2].y))//只在有點時更新答案! 否則答案會是它的x+y Ans[q[p2].type]=std::min(Ans[q[p2].type],q[p2].x+q[p2].y-val);tmp[t++]=q[p2++];}}if(p1<=m){for(int i=l; i<p1; ++i)if(!q[i].type) BIT::Clear(q[i].y);while(p1<=m) tmp[t++]=q[p1++];}else{while(p2<=r){if(q[p2].type)if(val=BIT::Query(q[p2].y))Ans[q[p2].type]=std::min(Ans[q[p2].type],q[p2].x+q[p2].y-val);tmp[t++]=q[p2++];}for(int i=l; i<=m; ++i)if(!q[i].type) BIT::Clear(q[i].y);}for(int i=0; i<t; ++i) q[l+i]=tmp[i];} }int main() {n=read(),m=read();int Xmax=0,Ymax=0;for(int x,y,i=1; i<=n; ++i)//非負坐標...x=read()+1,y=read()+1,Xmax=std::max(Xmax,x),Ymax=std::max(Ymax,y),q[++qcnt]=Operation(0,x,y);for(int t,x,y,i=1; i<=m; ++i)t=read(),x=read()+1,y=read()+1,Xmax=std::max(Xmax,x),Ymax=std::max(Ymax,y),q[++qcnt]=Operation(t==1?0:++acnt,x,y);++Xmax,++Ymax,BIT::Max=Ymax;for(int i=1; i<=acnt; ++i) Ans[i]=Xmax+Ymax;for(int i=1; i<=qcnt; ++i) A[i]=q[i];CDQ(1,qcnt);for(int i=1; i<=qcnt; ++i) q[i]=A[i];for(int i=1; i<=qcnt; ++i) q[i].x=Xmax-q[i].x;CDQ(1,qcnt);for(int i=1; i<=qcnt; ++i) q[i]=A[i];for(int i=1; i<=qcnt; ++i) q[i].y=Ymax-q[i].y;CDQ(1,qcnt);for(int i=1; i<=qcnt; ++i) q[i]=A[i];for(int i=1; i<=qcnt; ++i) q[i].x=Xmax-q[i].x,q[i].y=Ymax-q[i].y;CDQ(1,qcnt);for(int i=1; i<=acnt; ++i) printf("%d\n",Ans[i]);return 0; }

轉載于:https://www.cnblogs.com/SovietPower/p/8615025.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的BZOJ.2716.[Violet3]天使玩偶(CDQ分治 坐标变换)的全部內容，希望文章能夠幫你解決所遇到的問題。

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