2015年5月30日 星期六

[CF 487E] Tourists

作法:

這題的官方解大部份講的蠻清楚的,主要就是要先知道那個引理,然後把原圖的BCC樹建出來,對每塊縮完後的BCC(或是單一一個割點)維護那塊目前的最小值,然後對BCC樹作樹鍊剖分,讓他可以支援「修改點權與詢問某條路徑上點權最小值」這兩件事。但官方解裡提到的「只要更新其祖先的那塊BCC的值就好了」寫的不太清楚,這裡詳細解釋一下。

以下圖舉例,右邊是用BCC縮完點後的圖,其中紅色是割點,黑色的是一塊BCC。對於每個BCC都維護一個 multiset ,裡面裝的值是「在這個BCC內的點,除了他的祖先以外的所有點的值」,並且這坨BCC在新的樹當中的「點權」就會是這個 multiset 裡最小的數,割點在新的樹裡的點權則和原圖中的一樣。例如在下圖中,$2,3,4,5$這坨BCC在新的圖中他的點權就會是$2,3,4$的點權的最小值,$2,6,7$那坨則是$6,7$點權的最小值,其他以此類推。這樣就能在$O(logn)$的時間內完成修改了。具體方法是,如果改的點是割點的話,會動到的新圖中的點權有割點本身,還有他的父親BCC(如果他有父親的話一定是一坨BCC)。而如果改的點不是割點的話就只會動到他所屬的BCC的權值而已。

code :



#include<bits/stdc++.h>
#define INF 2000000000
using namespace std;
const int maxn=200000+10 ;
 
namespace seg_t
{
    struct node
    {
        node *l,*r ;
        int val ;
        node(){l=r=NULL ;}
    };
 
    void pull(node *u){u->val=min(u->l->val,u->r->val) ;}
 
    node *build(int l,int r)
    {
        if(l==r) return new node() ;
        node *u=new node() ;
        int mid=(l+r)/2 ;
        u->l=build(l,mid) ;
        u->r=build(mid+1,r) ;
        return u ;
    }
 
    void modify(int L,int R,node *u,int pos,int val)
    {
        if(L==R){ u->val=val ; return ; }
        int mid=(L+R)/2 ;
        if(pos<=mid) modify(L,mid,u->l,pos,val) ;
        else modify(mid+1,R,u->r,pos,val) ;
        pull(u) ;
    }
 
    int query(int l,int r,int L,int R,node *u)
    {
        if(l==L && r==R) { return u->val ; }
        int mid=(L+R)/2 ;
        if(r<=mid) return query(l,r,L,mid,u->l) ;
        else if(l>mid) return query(l,r,mid+1,R,u->r) ;
        else return min(query(l,mid,L,mid,u->l),
                        query(mid+1,r,mid+1,R,u->r)) ;
    }
}
 
namespace hld
{
    const int LOG=int(log2(maxn)+1) ;
    vector<int> v[maxn] ;
    int n ;
    int dep[maxn],anc[LOG][maxn] ;
    int tin[maxn],tout[maxn],tick ;
    int mson[maxn] ;
    int pid[maxn],head[maxn],chid[maxn],chcnt ;
    int chsz[maxn] ;
    int weight[maxn] ;
    seg_t::node *root[maxn] ;
 
    void add_edge(int x,int y)
    {
        v[y].push_back(x) ;
        v[x].push_back(y) ;
    }
 
    int dfs(int x,int f,int d)
    {
        tin[x]=tick++ ;
        dep[x]=d ; anc[0][x]=f ;
        for(int i=1;i<LOG;i++) anc[i][x]=anc[i-1][anc[i-1][x]] ;
        int ret=1,ma=-1 ;
        for(auto i : v[x]) if(i!=f)
        {
            int tmp=dfs(i,x,d+1) ;
            if(tmp>ma) ma=tmp , mson[x]=i ;
            ret+=tmp ;
        }
        tout[x]=tick++ ;
        return ret ;
    }
 
    void dfs(int x,int f)
    {
        if(x==f || mson[anc[0][x]]!=x)
        {
            pid[x]=0 ;
            head[x]=x ;
            chid[x]=chcnt++ ;
        }
        else
        {
            pid[x]=pid[f]+1 ;
            head[x]=head[f] ;
            chid[x]=chid[f] ;
        }
        chsz[chid[x]]=max(chsz[chid[x]],pid[x]+1) ;
        for(auto i : v[x]) if(i!=f) dfs(i,x) ;
    }
 
    inline bool isfa(int x,int y)
    {
        return tin[x]<=tin[y] && tout[x]>=tout[y] ;
    }
 
    int LCA(int x,int y)
    {
        if(isfa(x,y)) return x ;
        if(isfa(y,x)) return y ;
        for(int i=LOG-1;i>=0;i--) if(!isfa(anc[i][x],y))
            x=anc[i][x] ;
        return anc[0][x] ;
    }
 
    void build_HLD()
    {
        dfs(1,1,0) ;
        dfs(1,1) ;
        for(int i=0;i<chcnt;i++) root[i]=seg_t::build(0,chsz[i]-1) ;
        for(int i=1;i<=n;i++)
        {
            int id=chid[i] ;
            seg_t::modify(0,chsz[id]-1,root[id],pid[i],weight[i]) ;
        }
    }
 
    inline void modify(int x,int val)
    {
        int id=chid[x] ;
        seg_t::modify(0,chsz[id]-1,root[id],pid[x],val) ;
    }
 
    int query(int x,int y) /// y is fa of x
    {
        assert(isfa(y,x)) ;
        int id=chid[x] ;
        if(id==chid[y]) return
            seg_t::query(pid[y],pid[x],0,chsz[id]-1,root[id]) ;
        return min(seg_t::query(0,pid[x],0,chsz[id]-1,root[id]),
                   query(anc[0][head[x]],y)) ;
    }
}
 
vector<int> v[maxn] ;
int w[maxn] ;
int lev[maxn] ;
int cutid[maxn],bcc[maxn],ccnt,bcnt ;
vector<int> vb[maxn] ;
multiset<int> st[maxn] ;
stack<int> s ;
int dfs(int x,int f,int l)
{
    int low ; lev[x]=low=l ;
    s.push(x) ;
    int iscut=0,son=0 ;
    for(auto i : v[x]) if(i!=f)
    {
        if(lev[i]!=-1){low=min(low,lev[i]) ; continue ;}
        son++ ;
        int tmp=dfs(i,x,l+1) ; low=min(low,tmp) ;
        if(tmp>=l)
        {
            iscut=1 ; bcnt++ ;
            int top ;
            do
            {
                bcc[top=s.top()]=bcnt ;
                vb[bcnt].push_back(top) ;
                s.pop() ;
            }while(top!=i) ;
            bcc[x]=bcnt ; vb[bcnt].push_back(x) ;
        }
    }
    if((x!=f && iscut) || (x==f && son>1)) cutid[x]=++ccnt ;
    return low ;
}
 
int fa[maxn] ;
void dfs2(int x,int f) /// on new graph which is a tree
{
    fa[x]=f ;
    for(auto i : hld::v[x]) if(i!=f)
        dfs2(i,x) ;
}
 
main()
{
    int n,m,Q ; scanf("%d%d%d",&n,&m,&Q) ;
    for(int i=1;i<=n;i++) scanf("%d",&w[i]) ;
    while(m--)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        v[x].push_back(y) ;
        v[y].push_back(x) ;
    }
    memset(lev,-1,sizeof(lev)) ;
    dfs(1,1,0) ;
 
    hld::n=ccnt+bcnt ;
    for(int i=1;i<=bcnt;i++) for(auto j : vb[i]) if(cutid[j])
        hld::add_edge(cutid[j],i+ccnt) ;
    dfs2(1,1) ;
    for(int i=1;i<=n;i++) if(cutid[i])
        hld::weight[cutid[i]]=w[i] ;
    for(int i=1;i<=bcnt;i++)
    {
        for(auto j : vb[i]) if(!cutid[j] || fa[i+ccnt]!=cutid[j])
            st[i].insert(w[j]) ;
        hld::weight[i+ccnt]= *st[i].begin() ;
    }
    hld::build_HLD() ;
 
    while(Q--)
    {
        char c[5] ; int x,y ;
        scanf("%s%d%d",c,&x,&y) ;
        if(c[0]=='A')
        {
            if(x==y){printf("%d\n",w[x]) ; continue ;}
            x=(cutid[x] ? cutid[x] : bcc[x]+ccnt) ;
            y=(cutid[y] ? cutid[y] : bcc[y]+ccnt) ;
            int lca=hld::LCA(x,y) ;
            int ans=min(hld::query(x,lca),hld::query(y,lca)) ;
            if(lca!=1 && lca>ccnt)
                ans=min(ans,hld::query(fa[lca],fa[lca])) ;
            printf("%d\n",ans) ;
        }
        else if(cutid[x])
        {
            w[x]=y ; x=cutid[x] ;
            int tmp=hld::query(x,x) ;
            hld::modify(x,y) ;
            if(x==1) continue ;
            int bid=fa[x]-ccnt ;
            st[bid].erase(st[bid].find(tmp)) ;
            st[bid].insert(y) ;
            hld::modify(bid+ccnt,*st[bid].begin()) ;
        }
        else
        {
            int old=w[x] ; w[x]=y ;
            x=bcc[x] ;
            st[x].erase(st[x].find(old)) ;
            st[x].insert(y) ;
            hld::modify(x+ccnt,*st[x].begin()) ;
        }
    }
}
 

沒有留言:

張貼留言