首先對於任兩點$a$、$b$，可以發現，如果他們的對角線斜率$\geq 0$，曼哈頓距離就是$\left|(a.x+a.y)-(b.x+b.y)\right|$，否則就是$\left|(a.x-a.y)-(b.x-b.y)\right|$
因此，我們可以想到一種求解的方法：
對於詢問的每一點$q$，枚舉所有之前加進去的點$p$：
$if\ _{情況1}(p.x\leq q.x且p.y\leq q.y)或_{情況2}(p.x\geq q.x且p.y\geq q.y)$，更新$\left|(q.x+q.y)-(p.x+p.y)\right|$的最小值
$if\ _{情況3}(p.x\leq q.x且p.y\geq q.y)或_{情況4}(p.x\geq q.x且p.y\leq q.y)$，更新$\left|(q.x-q.y)-(p.x-p.y)\right|$的最小值
這樣時間複雜度就是$O(N^{2})$
不過可以發現，更新$\left|(q.x+q.y)-(p.x+p.y)\right|$或$\left|(q.x-q.y)-(p.x-p.y)\right|$的最小值的順序可以隨便排，那是否可以用某種順序更新他們的最小值來降低時間複雜度呢？
可以的！
假設我們要用一群點$P$來更新一群詢問$Q$，其中$P$和$Q$要滿足以下條件：在$Q$裡面的任何一個詢問之前，所有在$P$裡面的點都已經加入盤面中
因此，我們可以把$P$和$Q$依照$x$進行排序，為了方便說明，稱$p_{i}$為將$P$排序後，裡面的第$i$個點，$q_{i}$為將$Q$排序後，裡面的第$i$個點
因此對於每個$q_{i}$，可以把所有$p.x\leq q_{i}.x$的$p_{j}$慢慢加進線段樹維護(維護甚麼請看$_{註1}$)，這樣就可以$O(\log n)$求出所有$p.y\leq q_{i}.y$的$p_{j}$中，他們的$x+y$的最大值$max(x+y)$了，有沒有發現$(q_{i}.x+q_{i}.y)-max(x+y)$就是$_{情況1}$的最佳解呢？
可以保證，$q_{i}.x+q_{i}.y\geq max(x+y)$(想一想，為甚麼XD)
所以，$_{註1}$這線段樹要對$y$維護$x+y$的最大值，支持單點修改、區間查詢
同樣的：
對於$_{情況2}$：$x$由大到小枚舉$q_{i}$，用線段樹維護並取得$p.x\geq q_{i}.x$中$x+y$的最小值$min(x+y)$，最佳解就是$min(x+y)-(q_{i}.x+q_{i}.y)$
對於$_{情況3}$：$x$由小到大枚舉$q_{i}$，用線段樹維護並取得$p.x\leq q_{i}.x$中$x-y$的最大值$max(x-y)$，最佳解就是$(q_{i}.x-q_{i}.y)-max(x-y)$
對於$_{情況4}$：$x$由大到小枚舉$q_{i}$，用線段樹維護並取得$p.x\geq q_{i}.x$中$x-y$的最小值$min(x-y)$，最佳解就是$min(x-y)-(q_{i}.x-q_{i}.y)$
因此，要用$P$來更新$Q$，可以做到時間複雜度$O((P.size+Q.size)\log P.size)$
想像一下，如果我們依照時間將加入的點和詢問的點分類，對一個時間區間$[l,r]$，我們可以將這些點，時間$\leq \frac{l+r}{2}$的分一類，時間$>\frac{l+r}{2}$的分另外一類，這就很像線段樹的建樹過程 (稱Q-Tree吧) 一直二分時間區間，二分區間時 (遍歷順序也是後序) 用左區間中的插入操作 (上面所說的$P$) 更新右區間中的查詢操作 (上面所說的$Q$)
這樣一來，一段長度$n$時間區間最多遞迴分割$O(\log n)$層
假設這個時間區間內包含$p$個被加入的點和$q$個被詢問的點，處理Q-Tree的每一層均攤時間複雜度$O((p+q)\log(y的範圍))$
如果不知道哪來的時間區間，提示一下，全部的時間區間是$[1,N]$
注意，這裡忽略了初始化線段樹的時間成本，實際上，透過還原操作就不用再初始化第二次
假設總共加入$P$個點，詢問$Q$個點
總時間複雜度：$O((P+Q)\log(y的範圍)\log N)$
code:
因此，要用$P$來更新$Q$，可以做到時間複雜度$O((P.size+Q.size)\log P.size)$
想像一下，如果我們依照時間將加入的點和詢問的點分類，對一個時間區間$[l,r]$，我們可以將這些點，時間$\leq \frac{l+r}{2}$的分一類，時間$>\frac{l+r}{2}$的分另外一類，這就很像線段樹的建樹過程 (稱Q-Tree吧) 一直二分時間區間，二分區間時 (遍歷順序也是後序) 用左區間中的插入操作 (上面所說的$P$) 更新右區間中的查詢操作 (上面所說的$Q$)
這樣一來，一段長度$n$時間區間最多遞迴分割$O(\log n)$層
假設這個時間區間內包含$p$個被加入的點和$q$個被詢問的點，處理Q-Tree的每一層均攤時間複雜度$O((p+q)\log(y的範圍))$
如果不知道哪來的時間區間，提示一下，全部的時間區間是$[1,N]$
注意，這裡忽略了初始化線段樹的時間成本，實際上，透過還原操作就不用再初始化第二次
假設總共加入$P$個點，詢問$Q$個點
總時間複雜度：$O((P+Q)\log(y的範圍)\log N)$
code:
#include<cstdio> #include<cassert> #include<vector> #include<algorithm> using namespace std; const int INF=1000000000; void getmin(int &a,const int b){if(b<a)a=b;} void getmax(int &a,const int b){if(b>a)a=b;} class SegTree { private: int mn[4000000],mx[4000000]; void Build(const int id,const int l,const int r) { mn[id]=INF,mx[id]=-INF; if(l==r)return; const int mid=(l+r)/2; Build(id*2,l,mid),Build(id*2+1,mid+1,r); } void Maintain(const int id){mn[id]=min(mn[id*2],mn[id*2+1]),mx[id]=max(mx[id*2],mx[id*2+1]);} void Modify(const int id,const int l,const int r,const int loc,const int mn_val,const int mx_val) { if(l==r){assert(loc==r);getmin(mn[id],mn_val),getmax(mx[id],mx_val);return;} const int mid=(l+r)/2; if(loc<=mid)Modify(id*2,l,mid,loc,mn_val,mx_val); else Modify(id*2+1,mid+1,r,loc,mn_val,mx_val); Maintain(id); } void Reset(const int id,const int l,const int r) { if(mn[id]==INF&&mx[id]==-INF)return; if(l==r){mn[id]=INF,mx[id]=-INF;return;} const int mid=(l+r)/2; Reset(id*2,l,mid),Reset(id*2+1,mid+1,r); Maintain(id); assert(mn[id]==INF&&mx[id]==-INF); } int Query(const int id,const int l,const int r,const int bl,const int br,const bool is_mn)const { if(r<bl||br<l)return is_mn?INF:-INF; if(bl<=l&&r<=br)return is_mn?mn[id]:mx[id]; const int mid=(l+r)/2; const int lv=Query(id*2,l,mid,bl,br,is_mn),rv=Query(id*2+1,mid+1,r,bl,br,is_mn); return is_mn?min(lv,rv):max(lv,rv); } public: SegTree(){Build(1,1,1000000);} void Modify(const int loc,const int mn_val,const int mx_val){Modify(1,1,1000000,loc,mn_val,mx_val);} int QueryMin(const int bl,const int br)const{return Query(1,1,1000000,bl,br,true);} int QueryMax(const int bl,const int br)const{return Query(1,1,1000000,bl,br,false);} void Reset(){Reset(1,1,1000000);} }; struct Operation { int time,x,y; Operation(){} Operation(const int _time,const int _x,const int _y):time(_time),x(_x),y(_y){} }; bool CmpT(const Operation &a,const Operation &b){return a.time<b.time;} bool CmpY(const Operation &a,const Operation &b){return a.y<b.y;} int N,ANS[200000]; void Query(const vector<Operation>&ope_add,const vector<Operation>&ope_que,const int l,const int r,SegTree &seg_tree) { if(ope_add.empty()||ope_que.empty())return; const int mid=(l+r)/2; vector<Operation>ch_ope_add[2],ch_ope_que[2]; for(const Operation &o:ope_add)ch_ope_add[o.time>mid].push_back(o); for(const Operation &o:ope_que)ch_ope_que[o.time>mid].push_back(o); if(true) { auto &ope=ch_ope_add[0],&que=ch_ope_que[1]; sort(ope.begin(),ope.end(),CmpY); sort(que.begin(),que.end(),CmpY); if(true) { int i=-1; for(const Operation &q:que) { while(i+1<(int)ope.size()&&ope[i+1].y<=q.y) { i++,seg_tree.Modify(ope[i].x,ope[i].x-ope[i].y,ope[i].x+ope[i].y); } getmin(ANS[q.time],seg_tree.QueryMin(q.x,1000000)-(q.x-q.y)); getmin(ANS[q.time],(q.x+q.y)-seg_tree.QueryMax(1,q.x)); } seg_tree.Reset(); } for(int l=0,r=(int)ope.size()-1;l<r;l++,r--)swap(ope[l],ope[r]); for(int l=0,r=(int)que.size()-1;l<r;l++,r--)swap(que[l],que[r]); if(true) { int i=-1; for(const Operation &q:que) { while(i+1<(int)ope.size()&&ope[i+1].y>=q.y) { i++,seg_tree.Modify(ope[i].x,ope[i].x+ope[i].y,ope[i].x-ope[i].y); } getmin(ANS[q.time],seg_tree.QueryMin(q.x,1000000)-(q.x+q.y)); getmin(ANS[q.time],(q.x-q.y)-seg_tree.QueryMax(1,q.x)); } seg_tree.Reset(); } sort(ope.begin(),ope.end(),CmpT); sort(que.begin(),que.end(),CmpT); } Query(ch_ope_add[0],ch_ope_que[0],l,mid,seg_tree); Query(ch_ope_add[1],ch_ope_que[1],mid+1,r,seg_tree); } int main() { // freopen("in.txt","r",stdin); int testcount;scanf("%d",&testcount); while(testcount--) { scanf("%d",&N); vector<Operation>ope_add,ope_que; for(int i=0,type,x,y;i<N;i++) { scanf("%d%d%d",&type,&x,&y); (type==0?ope_add:ope_que).push_back(Operation(i,x,y)); if(type==1)ANS[i]=INF; } static SegTree seg_tree=SegTree(); Query(ope_add,ope_que,0,N-1,seg_tree); for(const Operation &o:ope_que)printf("%d\n",ANS[o.time]); } return 0; }
<(_ _)>
回覆刪除<(_ _)>
刪除