487E - Tourists - CodeForces Solution

#include<bits/stdc++.h>
#define ll long long
#define db double
#define ull unsigned ll
#define ldb long db
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<db,db>
#define F first
#define S second
#define pb push_back
using namespace std;
const int N=2e5+5,inf=1e9;
int n,m,q,w[N],u,v,col,dfn[N],low[N],Siz,dep[N],fa[N],top[N],siz[N],son[N],id[N],tr[N*4];
vector<int> g[N],e[N];
stack<int> st;
multiset<int> val[N];
string opt;
void chmin(int &x,int y){
	if(x>y) x=y;
}
void tarjan(int cur,int pa){
	dfn[cur]=low[cur]=++Siz;
	st.push(cur);
	for(int to:g[cur]) if(to!=pa){
		if(!dfn[to]){
			tarjan(to,cur);
			chmin(low[cur],low[to]);
			if(dfn[cur]<=low[to]){
				++col;
				e[cur].pb(n+col);
				e[n+col].pb(cur);
				e[to].pb(n+col);
				e[n+col].pb(to);
				while(st.top()!=to){
					e[st.top()].pb(n+col);
					e[n+col].pb(st.top());
					st.pop();
				}
				st.pop();
			}
		}
		else chmin(low[cur],dfn[to]);
	}
}
void dfs(int cur,int pa){
	fa[cur]=pa;
	dep[cur]=dep[pa]+1;
	siz[cur]=1;
	for(int to:e[cur]) if(to!=pa){
		dfs(to,cur);
		siz[cur]+=siz[to];
		if(siz[to]>siz[son[cur]]) son[cur]=to;
	}
}
void dfs1(int cur,int tp){
	id[cur]=++Siz;
	top[cur]=tp;
	if(!son[cur]) return;
	dfs1(son[cur],tp);
	for(int to:e[cur]) if(!top[to]) dfs1(to,to);
}
void pushup(int x){
	tr[x]=min(tr[x<<1],tr[x<<1|1]);
}
void updt(int x,int l,int r,int p,int c){
	if(l==r){
		tr[x]=c;
		return;
	}
	int mid=(l+r)>>1;
	if(p<=mid) updt(x<<1,l,mid,p,c);
	else updt(x<<1|1,mid+1,r,p,c);
	pushup(x);
}
int query(int x,int l,int r,int L,int R){
	if(L<=l && r<=R) return tr[x];
	int mid=(l+r)>>1,res=inf;
	if(L<=mid) chmin(res,query(x<<1,l,mid,L,R));
	if(R>mid) chmin(res,query(x<<1|1,mid+1,r,L,R));
	return res;
}
int getlca(int x,int y){
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]) swap(x,y);
		y=fa[top[y]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	return x;
}
int ask(int x,int y){
	int res=inf;
	while(top[x]!=top[y]){
		if(dep[top[x]]>dep[top[y]]) swap(x,y);
		chmin(res,query(1,1,n+col,id[top[y]],id[y]));
		y=fa[top[y]];
	}
	if(dep[x]>dep[y]) swap(x,y);
	chmin(res,query(1,1,n+col,id[x],id[y]));
	return res;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m>>q;
	for(int i=1;i<=n;++i) cin>>w[i];
	while(m--){
		cin>>u>>v;
		g[u].pb(v);
		g[v].pb(u);
	}
	tarjan(1,0);
	dfs(1,0);
	Siz=0; dfs1(1,1);
	for(int i=1;i<=n;++i) val[fa[i]].insert(w[i]);
	for(int i=n+1;i<=n+col;++i) w[i]=(*val[i].begin());
	for(int i=1;i<=n+col;++i) updt(1,1,n+col,id[i],w[i]);
	while(q--){
		cin>>opt>>u>>v;
		if(opt[0]=='C'){
			val[fa[u]].erase(val[fa[u]].find(w[u]));
			val[fa[u]].insert(v);
			w[fa[u]]=(*val[fa[u]].begin());
			updt(1,1,n+col,id[u],v);
			if(fa[u]) updt(1,1,n+col,id[fa[u]],w[fa[u]]);
			w[u]=v;
		}
		else{
			int l=getlca(u,v),ans=inf;
			if(l>n) ans=w[fa[l]];
			chmin(ans,ask(u,v));
			cout<<ans<<'\n';
		}
	}
	return 0;
}
//Arcana.