\(\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)\)。
\(\mathcal{Code}\)
#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;
}