codeforces 487E Tourists : 圓方樹+鍊剖+線段樹+可删除堆

題意：

給出一個無向聯通圖，每個點有一個權值，要求茲磁一種修改操作：修改某點權值；以及一種查詢操作：查詢某兩點x，y的所有簡單路徑上的最小點權。

題解：

這東西是必然要縮點的啦，那麼問題來了，縮點有三種寫法：強連通，點雙，邊雙。顯然要點雙啦，題目都說了要簡單路徑的。那麼點雙一縮，變成一棵樹，然後考慮樹上兩點，他們的簡單路徑并={樹上路徑+路徑上的點雙裡面的所有的點}。我們仿照圓方樹操作：将每個點雙建立一個方點，用來代表這一整個點雙，他的權值為這個點雙裡邊所有點的最小點權。

那麼查詢就是樹上路徑的最小點權查詢，鍊剖+線段樹切之。

考慮到要進行修改操作，不能讓方點代表整個點雙，因為一個圓點可以同時在很多點雙中。是以我們可以讓每一個方點隻代表他所有兒子。這樣每次隻會修改一個方點。這樣查詢的時候，如果lca是一個方點，那麼我們隻需要再把方點的父親圓點比較以下就可以了。

每一個方點我們需要使用可删除堆之類的結構維護他代表的所有點。比如一個map操作之類的。友善的修改一個值以及取到最小值。

Code：

#include<bits/stdc++.h>
#define PB(x) push_back(x)
using namespace std;
const int maxn = +;
const int INF = ;
vector<int> E[maxn],ET[maxn];
int n,m,q;int N;
int a[maxn],mapid[maxn],mapCnt;
bool inCircle[maxn];int bcc_no[maxn];
map<int,int> cnt[maxn];
int dfn[maxn],low[maxn],dfs_clock,fa[maxn];
int sz[maxn*],wson[maxn*],top[maxn*],dep[maxn*],pos[maxn*];
char s[];
pair<int,int> stk[maxn*];int topp;
struct Seg_Tree{
    int val[maxn*],cnt=;
    inline void up(int x){
        val[x] = min(val[x<<],val[x<<|]);
    }
    void modify(int x,int l,int r,int Index,int Val){
        if (l==r){
            val[x] =Val;
            return;
        }
        int mid = l+r >>;
        if (Index<=mid)modify(x<<,l,mid,Index,Val);
        else modify(x<<|,mid+,r,Index,Val);
        up(x);
    }
    int query(int x,int l,int r,int L,int R){
        if (l>R||r<L)return INF;
        if (L<=l&&r<=R)return val[x];
        int mid = l+r >>;
        return min(query(x<<,l,mid,L,R),query(x<<|,mid+,r,L,R));
    }
}tree;
void input(){
    scanf("%d%d%d",&n,&m,&q);
    N =n;
    for (int i=;i<=n;i++){
        scanf("%d",a+i);
    }
    for (int i=;i<m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        E[u].PB(v);E[v].PB(u);
    }
}
void tarjan(int u,int fa,pair<int,int>Eid){
    dfn[u] = low[u] = ++dfs_clock;
    for (int i=;i<E[u].size();i++){
        int v = E[u][i];
        if (v==fa)continue;
        if (!dfn[v]){
            stk[topp++] = {u,v};
            tarjan(v,u,{u,v});
            low[u] = min(low[u],low[v]);
            if (low[v]==dfn[u]){
                n++;
                mapid[n-N] = ++mapCnt;
                ET[u].PB(n);
                while (true){
                    pair<int,int> tt = stk[--topp];
                    if (bcc_no[tt.second]!=n){
                        bcc_no[tt.second] =n;
                        if (tt.second!=u)
                        ET[n].PB(tt.second),cnt[mapid[n-N]][a[tt.second]]++;

                    }
                    if (tt==(pair<int,int>){u,v})break;
                }
            }
        }else if (dfn[v]<dfn[u]){
            stk[topp++] = {u,v};
            low[u] = min(low[u],dfn[v]);
        }
    }
    if (stk[topp-]==Eid)topp--,ET[Eid.first].PB(Eid.second);
}
void dfs1(int u){
    sz[u]=;
    dep[u] =dep[fa[u]]+;
    for (int i=;i<ET[u].size();i++){
        int v = ET[u][i];
        fa[v]=u;
        dfs1(v);
        sz[u]+=sz[v];
        if (sz[v]>sz[wson[u]])wson[u] =v;
    }
}
void dfs2(int u,int chain){
    pos[u] = ++tree.cnt;
    top[u] = chain;
    if (fa[u]>N){
        a[fa[u]] = min(a[fa[u]],a[u]);
    }
    if (wson[u])dfs2(wson[u],chain);
    for (int i=;i<ET[u].size();i++){
        int v = ET[u][i];
        if (v==fa[u]||v==wson[u])continue;
        dfs2(v,v);
    }
    tree.modify(,,n,pos[u],a[u]);
}
void build(){
    tarjan(,,{,});
    dfs1();
    dfs2(,);
}
int query(int x,int y){
    if (x==y)return a[x];
    int ret = INF;
    while (top[x]!=top[y]){
        if (dep[top[x]]<dep[top[y]]){
            swap(x,y);
        }
        ret = min(ret,tree.query(,,n,pos[top[x]],pos[x]));
        x = fa[top[x]];
    }
    if(dep[x]<dep[y])swap(x,y);
    ret = min(ret,tree.query(,,n,pos[y],pos[x]));
    if (y>N){
        ret = min(ret,a[fa[y]]);
    }
    return ret;
}
void solve(){
    while (q--){
        int x,y;
        scanf("%s%d%d",s,&x,&y);
        if (s[]=='A'){
            printf("%d\n",query(x,y));
        }else{
            tree.modify(,,n,pos[x],y);
            if (fa[x]>N){
                cnt[mapid[fa[x]-N]][a[x]]--;
                if (cnt[mapid[fa[x]-N]][a[x]]==){
                    cnt[mapid[fa[x]-N]].erase(a[x]);
                }
                cnt[mapid[fa[x]-N]][y]++;
                int temp=(*cnt[mapid[fa[x]-N]].begin()).first;
                if (temp!=a[fa[x]]){
                    a[fa[x]]=temp;
                    tree.modify(,,n,pos[fa[x]],temp);
                }
            }
            a[x]=y;
        }
    }
}
int main(){
    memset(a,INF,sizeof a);
    input();
    build();
    solve();
    return ;
}