【CodeForces 487E】Tourists / 题解

题目描述

求简单无向图两点路径上最小权值,支持修改。

思路

先把图中的点双缩点,维护圆方树,把方点的值设为它儿子中点权最小的点的点权,树链剖分。利用 Multiset 维护每个点双的信息即可。

代码

#include 
#define ls (p<<1)
#define rs (p<<1|1)
#define maxn 100010
#define mid ((l+r)>>1)
#define ll long long
#define inf INT_MAX
using namespace std;
int n,m,q,val[maxn<<2],pointsum;
multisetst[maxn<<2];
struct ios{
    inline char read(){
        static const int IN_LEN=1<<18|1;
        static char buf[IN_LEN],*s,*t;
        return (s==t)&&(t=(s=buf)+fread(buf,1,IN_LEN,stdin)),s==t?-1:*s++;
    }
    template  inline ios & operator >> (_Tp&x){
        static char c11,boo;
        for(c11=read(),boo=0;!isdigit(c11);c11=read()){
            if(c11==-1)return *this;
            boo|=c11=='-';
        }
        for(x=0;isdigit(c11);c11=read())x=x*10+(c11^'0');
        boo&&(x=-x);
        return *this;
    }
}io;
struct Edge{
    int to,next;
    Edge(int a=0,int b=0){
        to=a,next=b;
    }
};
struct Graph{
    Edge l[maxn<<2];
    int head[maxn<<1],cnt,ind;
    int fa[maxn<<1],son[maxn<<1];
    int top[maxn<<1],dep[maxn<<1];
    int siz[maxn<<1],id[maxn<<1];
    int rid[maxn<<1];
    void Add(int a,int b){
        l[++cnt]=Edge(b,head[a]);head[a]=cnt;
        l[++cnt]=Edge(a,head[b]);head[b]=cnt;
    }
    void Pre_Work(int u,int f){
        fa[u]=f,siz[u]=1,dep[u]=dep[f]+1;
        int maxson=-1;
        for (int i=head[u];i;i=l[i].next){
            int v=l[i].to;
            if (v==f) continue;
            Pre_Work(v,u);
            siz[u]+=siz[v];
            if (siz[v]>maxson)
                maxson=siz[v],son[u]=v;
        }
    }
    void Re_Build(int u,int topf){
        top[u]=topf;rid[id[u]=++ind]=u;
        if (son[u]) Re_Build(son[u],topf);
        for (int i=head[u];i;i=l[i].next){
            int v=l[i].to;
            if (v==fa[u]||v==son[u]) continue;
            Re_Build(v,v);
        }
    }
    int tree[maxn<<4];
    void Pushup(int p){
        tree[p]=min(tree[ls],tree[rs]);
    }
    void Build(int l,int r,int p){
        if (l==r){tree[p]=val[rid[l]];return;}
        Build(l,mid,ls),Build(mid+1,r,rs);
        Pushup(p);
    }
    void Update(int l,int r,int t,int v,int p){
        if (l==r){tree[p]=v;return;}
        if (t<=mid) Update(l,mid,t,v,ls);
        else Update(mid+1,r,t,v,rs);
        Pushup(p);
    }
    int Query(int l,int r,int L,int R,int p){
        if (l>R||r=L&&r<=R) return tree[p];
        return min(Query(l,mid,L,R,ls),Query(mid+1,r,L,R,rs));
    }
    int Path_Query(int x,int y){
        int res=inf;
        while(top[x]!=top[y]){
            if (dep[top[x]]dep[y]) swap(x,y);
        res=min(res,Query(1,pointsum,id[x],id[y],1));
        if (x>n) res=min(res,val[fa[x]]);
        return res;
    }
}G;
struct DAG{
    Edge l[maxn<<1];
    int head[maxn],cnt;
    int dfn[maxn],low[maxn];
    int sta[maxn],ind,top;
    void Add(int a,int b){
        l[++cnt]=Edge(b,head[a]);
        head[a]=cnt;
    }
    void Tarjan(int u){
        low[u]=dfn[u]=++ind;
        sta[++top]=u;
        for (int i=head[u];i;i=l[i].next){
            int v=l[i].to;  
            if (!dfn[v]){
                Tarjan(v);
                low[u]=min(low[u],low[v]);
                if (low[v]>=dfn[u]){
                    int j=-1;pointsum++;
                    while(j!=v){
                        j=sta[top--];
                        G.Add(j,pointsum);
                    }
                    G.Add(u,pointsum);
                }
            }
            else low[u]=min(low[u],dfn[v]);
        }
    }
}D;
int main(){
    scanf("%d%d%d",&n,&m,&q);
    pointsum=n;
    for (int i=1;i<=n;i++) scanf("%d",val+i);
    for (int i=1,x,y;i<=m;i++){
        scanf("%d%d",&x,&y);
        D.Add(x,y),D.Add(y,x);
    }
    for (int i=1;i<=n;i++)
        if (!D.dfn[i]) D.Tarjan(i);
    G.Pre_Work(1,0),G.Re_Build(1,1);
    for (int i=2;i<=n;i++)
        st[G.fa[i]-n].insert(val[i]);
    for (int i=n+1;i<=pointsum;i++)
        val[i]=st[i-n].empty()?inf:*st[i-n].begin();
    G.Build(1,pointsum,1);
    for (int i=1,x,y;i<=q;i++){
        char op[2];
        scanf("%s%d%d",op,&x,&y);
        if (op[0]=='C'){
            G.Update(1,pointsum,G.id[x],y,1);
            if (x==1) {val[x]=y;continue;}
            int t=G.fa[x];
            st[t-n].erase(st[t-n].find(val[x]));
            st[t-n].insert(y);
            int mt=*st[t-n].begin();
            if (mt==val[t]) {val[x]=y;continue;}
            G.Update(1,pointsum,G.id[t],mt,1);
            val[t]=mt;val[x]=y;
        }
        if (op[0]=='A'){
            printf("%d\n",G.Path_Query(x,y));
        }
    }
    return 0;
}