```cpp
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<set>
#include<iomanip>
#include<cstring>
#define reg register
#define EN std::puts("")
#define LL long long
inline int read(){
register int x=0;register int y=1;
register char c=std::getchar();
while(c<'0'||c>'9'){if(c=='-') y=0;c=std::getchar();}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=std::getchar();}
return y?x:-x;
}
#define N 200006
#define M 200006
int n,m;
int w[N];
std::multiset<int>set[N];
struct graph{
int fir[N],nex[M],to[M],tot;
inline void add(int u,int v){
to[++tot]=v;
nex[tot]=fir[u];fir[u]=tot;
}
}G,T;
struct get_bcc{
int top,stack[N];
int dfn[N],low[N],dfscnt;
int bcccnt;
void tarjan(int u){
dfn[u]=low[u]=++dfscnt;stack[top++]=u;
for(reg int v,i=G.fir[u];i;i=G.nex[i]){
v=G.to[i];
if(!dfn[v]){
tarjan(v);low[u]=std::min(low[u],low[v]);
if(low[v]>=dfn[u]){
bcccnt++;
do{
T.add(bcccnt,stack[--top]);T.add(stack[top],bcccnt);
}while(stack[top]^v);
T.add(bcccnt,u);T.add(u,bcccnt);
}
}
else low[u]=std::min(low[u],dfn[v]);
}
}
}BCC;
struct TREE{
int fa[N],deep[N],size[N],son[N],index[N];
int top[N],dfn[N],dfscnt;
void dfs1(int u,int fat){
fa[u]=fat;deep[u]=deep[fat]+1;size[u]=1;
for(reg int v,i=T.fir[u];i;i=T.nex[i]){
v=T.to[i];
if(v!=fat){
dfs1(v,u);size[u]+=size[v];
if(size[v]>size[son[u]]) son[u]=v;
}
}
}
void dfs2(int u,int topnow){
top[u]=topnow;dfn[u]=++dfscnt;index[dfscnt]=u;
if(!son[u]) return;
dfs2(son[u],topnow);
for(reg int v,i=T.fir[u];i;i=T.nex[i]){
v=T.to[i];
if(!dfn[v]) dfs2(v,v);
}
}
struct tr {
tr *ls,*rs;
int min;
}dizhi[N<<1],*root=&dizhi[0];
int tot;
inline void pushup(tr *tree){tree->min=std::min(tree->ls->min,tree->rs->min);}
void build(tr *tree,int l,int r){
if(l==r) return tree->min=w[index[l]],void();
int mid=(l+r)>>1;
tree->ls=&dizhi[++tot];tree->rs=&dizhi[++tot];
build(tree->ls,l,mid);build(tree->rs,mid+1,r);
pushup(tree);
}
void change(tr *tree,int l,int r,int pos,int k){
if(l==r) return tree->min=k,void();
int mid=(l+r)>>1;
if(pos<=mid) change(tree->ls,l,mid,pos,k);
else change(tree->rs,mid+1,r,pos,k);
pushup(tree);
}
int get_min(tr *tree,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr) return tree->min;
int mid=(l+r)>>1;
if(qr<=mid) return get_min(tree->ls,l,mid,ql,qr);
if(ql>mid) return get_min(tree->rs,mid+1,r,ql,qr);
return std::min(get_min(tree->ls,l,mid,ql,qr),get_min(tree->rs,mid+1,r,ql,qr));
}
inline int find(int x,int y){
int ret=0x7f7f7f7f;
while(top[x]!=top[y]){
if(deep[top[x]]<deep[top[y]]) x^=y,y^=x,x^=y;
ret=std::min(ret,get_min(root,1,BCC.bcccnt,dfn[top[x]],dfn[x]));
x=fa[top[x]];
}
if(deep[x]>deep[y]) x^=y,y^=x,x^=y;
ret=std::min(ret,get_min(root,1,BCC.bcccnt,dfn[x],dfn[y]));
if(x>n) ret=std::min(ret,w[fa[x]]);
return ret;
}
}Tree;
int main(){
BCC.bcccnt=n=read();m=read();int q=read();
for(reg int i=1;i<=n;i++) w[i]=read();
for(reg int u,v,i=1;i<=m;i++){
u=read();v=read();
G.add(u,v);G.add(v,u);
}
BCC.tarjan(1);
Tree.dfs1(1,0);Tree.dfs2(1,1);
for(reg int i=1;i<=n;i++) set[Tree.fa[i]-n].insert(w[i]);
for(reg int i=n+1;i<=BCC.bcccnt;i++)
w[i]=set[i-n].empty()?0x7f7f7f7f:*set[i-n].begin();
Tree.build(Tree.root,1,BCC.bcccnt);
reg int x,y;char op;
while(q--){
std::scanf("%c",&op);
x=read();y=read();
if(op=='C'){
Tree.change(Tree.root,1,BCC.bcccnt,Tree.dfn[x],y);
if(x==1){w[1]=y;continue;}
int ind=Tree.fa[x]-n;
set[ind].erase(set[ind].find(w[x]));
set[ind].insert(y);
int min=*set[ind].begin();
w[x]=y;
if(min!=w[ind+n]) Tree.change(Tree.root,1,BCC.bcccnt,Tree.dfn[ind+n],min);
w[ind+n]=min;
}
else std::printf("%d\n",Tree.find(x,y));
}
return 0;
}
```
by suxxsfe @ 2020-04-24 11:43:39
~~题目名瞩目~~
by Velix @ 2020-04-24 11:54:25
好吧我似乎找到hack数据了,之前生成错了【捂脸】
by suxxsfe @ 2020-04-24 11:58:03
艹,又TLE on #21了/kk
by suxxsfe @ 2020-04-24 12:14:05
@[朕是蒟蒻](/user/239358) 同意
by ⚡小林子⚡ @ 2020-04-24 12:17:38
好吧我过了
枚举区间错(RE)+数组开小(TLE)
~~我太菜了~~
by suxxsfe @ 2020-04-24 12:18:11