2016年2月4日 星期四

[IOI Camp Judge 37]動態曼哈頓最短距離

IOI Camp Judge是暫時性的,因此我在這裡做了題目備份

首先對於任兩點$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:
#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;
}

2 則留言:

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原