\(\mathcal{Description}\)

  Link.

  维护一个 \(n\) 个点 \(m\) 条边的简单无向连通图，点有点权。\(q\) 次操作：

• 修改单点点权。

• 询问两点所有可能路径上点权的最小值。

    \(n,m,q\le10^5\)。

\(\mathcal{Solution}\)

  怎么可能维护图嘛，肯定是维护圆方树咯！

  一个比较 naive 的想法是，每个方点维护其邻接圆点的最小值，树链剖分处理询问。

  不过修改的复杂度会由于菊花退化：修改”花蕊“的圆点，四周 \(\mathcal O(n)\) 个方点的信息都需要修改。

  联想到 array 这道题，我们尝试”弱化“方点所维护的信息。每个方点，维护其圆方树上儿子们的点权最小值。那么每次修改圆点，至多就只有其父亲需要修改信息了。

  于是，每个方点用 std::multiset 或者常见的双堆 trick 维护最小值信息（推荐后者，常数较小），再用一样的树剖处理询问即可。

  复杂度 \(\mathcal O(n\log^2n)\)。

#include <queue>
#include <cstdio>

#define adj( g, u, v ) \
    for ( int eid = g.head[u], v; v = g.to[eid], eid; eid = g.nxt[eid] )

const int MAXN = 2e5, MAXM = 4e5;
int n, m, q, val[MAXN + 5], snode;
int dfc, tp, dfn[MAXN + 5], low[MAXN + 5], stk[MAXN + 5];
int siz[MAXN + 5], dep[MAXN + 5], fa[MAXN + 5], son[MAXN + 5];
int top[MAXN + 5];

inline bool chkmin ( int& a, const int b ) { return b < a ? a = b, true : false; }

struct Graph {
    int ecnt, head[MAXN + 5], to[MAXM + 5], nxt[MAXM + 5];
    inline void link ( const int s, const int t ) {
        to[++ ecnt] = t, nxt[ecnt] = head[s];
        head[s] = ecnt;
    }
    inline void add ( const int u, const int v ) {
        link ( u, v ), link ( v, u );
    }
} src, tre;

struct Heap {
    std::priority_queue<int, std::vector<int>, std::greater<int> > val, rem;
    inline void push ( const int ele ) { val.push ( ele ); }
    inline void pop ( const int ele ) { rem.push ( ele ); }
    inline int top () {
        for ( ; ! val.empty () && ! rem.empty () && val.top () == rem.top (); val.pop (), rem.pop () );
        return val.empty () ? -1 : val.top ();
    }
} heap[MAXN * 2 + 5];

struct SegmentTree {
    int mn[MAXN << 3];
    inline void pushup ( const int rt ) { chkmin ( mn[rt] = mn[rt << 1], mn[rt << 1 | 1] ); }
    inline void update ( const int rt, const int l, const int r, const int x, const int v ) {
        if ( l == r ) return void ( mn[rt] = v );
        int mid = l + r >> 1;
        if ( x <= mid ) update ( rt << 1, l, mid, x, v );
        else update ( rt << 1 | 1, mid + 1, r, x, v );
        pushup ( rt );
    }
    inline int query ( const int rt, const int l, const int r, const int ql, const int qr ) {
        if ( ql <= l && r <= qr ) return mn[rt];
        int ret = 2e9, mid = l + r >> 1;
        if ( ql <= mid ) chkmin ( ret, query ( rt << 1, l, mid, ql, qr ) );
        if ( mid < qr ) chkmin ( ret, query ( rt << 1 | 1, mid + 1, r, ql, qr ) );
        return ret;
    }
} st;

inline void Tarjan ( const int u, const int f ) {
    dfn[u] = low[u] = ++ dfc, stk[++ tp] = u;
    adj ( src, u, v ) if ( v ^ f ) {
        if ( ! dfn[v] ) {
            Tarjan ( v, u ), chkmin ( low[u], low[v] );
            if ( low[v] >= dfn[u] ) {
                tre.add ( u, ++ snode );
                do {
                    tre.add ( snode, stk[tp] );
                    heap[snode].push ( val[stk[tp]] );
                } while ( stk[tp --] ^ v );
            }
        } else chkmin ( low[u], dfn[v] );
    }
}

inline void DFS1 ( const int u, const int f ) {
    dep[u] = dep[fa[u] = f] + 1, siz[u] = 1;
    adj ( tre, u, v ) if ( v ^ f ) {
        DFS1 ( v, u ), siz[u] += siz[v];
        if ( siz[v] > siz[son[u]] ) son[u] = v;
    }
}

inline void DFS2 ( const int u, const int tp ) {
    top[u] = tp, dfn[u] = ++ dfc;
    if ( son[u] ) DFS2 ( son[u], tp );
    adj ( tre, u, v ) if ( v ^ fa[u] && v ^ son[u] ) DFS2 ( v, v );
}

inline int queryChain ( int u, int v ) {
    int ret = 2e9;
    while ( top[u] ^ top[v] ) {
        if ( dep[top[u]] < dep[top[v]] ) u ^= v ^= u ^= v;
        chkmin ( ret, st.query ( 1, 1, snode, dfn[top[u]], dfn[u] ) );
        u = fa[top[u]];
    }
    if ( dep[u] < dep[v] ) u ^= v ^= u ^= v;
    chkmin ( ret, st.query ( 1, 1, snode, dfn[v], dfn[u] ) );
    if ( v > n && fa[v] ) chkmin ( ret, val[fa[v]] );
    return ret;
}

int main () {
    scanf ( "%d %d %d", &n, &m, &q ), snode = n;
    for ( int i = 1; i <= n; ++ i ) scanf ( "%d", &val[i] );
    for ( int i = 1, u, v; i <= m; ++ i ) {
        scanf ( "%d %d", &u, &v );
        src.add ( u, v );
    }
    Tarjan ( 1, 0 ), dfc = 0;
    DFS1 ( 1, 0 ), DFS2 ( 1, 1 );
    for ( int i = 1; i <= n; ++ i ) st.update ( 1, 1, snode, dfn[i], val[i] );
    for ( int i = n + 1; i <= snode; ++ i ) st.update ( 1, 1, snode, dfn[i], heap[i].top () );
    char op[5]; int a, b;
    for ( ; q --; ) {
        scanf ( "%s %d %d", op, &a, &b );
        if ( op[0] == 'C' ) {
            st.update ( 1, 1, snode, dfn[a], b );
            if ( fa[a] ) {
                heap[fa[a]].pop ( val[a] );
                heap[fa[a]].push ( b );
                st.update ( 1, 1, snode, dfn[fa[a]], heap[fa[a]].top () );
            }
            val[a] = b;
        } else {
            printf ( "%d\n", queryChain ( a, b ) );
        }
    }
    return 0;
}