\(Tarjan\) 求出点双对应的圆方树,答案即是两点间的链上所有点双中的最小值。

注意到如果修改割点的话,他属于很多个点双,不能暴力。

其实只要让方点的值为所有儿子圆点的最小值即可,这样就只需修改父亲和自己。

树剖维护就好了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include<cstdio>
#include<set>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=200005,maxe=maxn*2;
int n,m,Q,a[maxn],w[maxn];
multiset<int> S[maxn];
int fir[maxn],nxt[maxe],son[maxe],tot=1;
void add(int x,int y){
son[++tot]=y; nxt[tot]=fir[x]; fir[x]=tot;
}
int dfn[maxn],low[maxn],Tim,stk[maxn],bcc;
struct Edge{
int x,y;
Edge(int t1=0,int t2=0){ x=t1; y=t2; }
} Es[maxe];
void Tarjan(int x,int fa_e){
dfn[x]=low[x]=++Tim; stk[++stk[0]]=x;
for(int j=fir[x];j;j=nxt[j])
if(!dfn[son[j]]){
Tarjan(son[j],j); low[x]=min(low[x],low[son[j]]);
if(low[son[j]]>=dfn[x]){
bcc++;
Es[++m]=Edge(n+bcc,x);
do{
Es[++m]=Edge(n+bcc,stk[stk[0]]);
S[n+bcc].insert(w[stk[stk[0]]]);
}while(stk[stk[0]--]!=son[j]);
}
} else if(j!=(fa_e^1)) low[x]=min(low[x],dfn[son[j]]);
}
int dep[maxn],sz[maxn],hvy[maxn],pre[maxn],top[maxn];
void dfs(int x){
sz[x]=1;
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre[x]){
dep[son[j]]=dep[x]+1; pre[son[j]]=x; dfs(son[j]);
sz[x]+=sz[son[j]]; if(sz[hvy[x]]<sz[son[j]]) hvy[x]=son[j];
}
}
int c[maxn],pos[maxn];
void Build_Chain(int x,int tp){
c[++c[0]]=x; pos[x]=c[0]; top[x]=tp;
if(hvy[x]) Build_Chain(hvy[x],tp);
for(int j=fir[x];j;j=nxt[j])
if(son[j]!=pre[x]&&son[j]!=hvy[x]) Build_Chain(son[j],son[j]);
}

int N_seg,ch[maxn*2][2],Min[maxn*2];
void maintain(int p){
Min[p]=min(Min[ch[p][0]],Min[ch[p][1]]);
}
int Build(int L,int R){
int p=++N_seg; Min[p]=2e9;
if(L==R) return Min[p]=w[c[L]], p;
int mid=(L+R)>>1;
ch[p][0]=Build(L,mid); ch[p][1]=Build(mid+1,R);
maintain(p); return p;
}
void Update(int p,int L,int R,int pos,int val){
if(pos<L||R<pos) return;
if(L==R) return Min[p]=val,void();
int mid=(L+R)>>1;
Update(ch[p][0],L,mid,pos,val); Update(ch[p][1],mid+1,R,pos,val);
maintain(p);
}
int Query(int p,int L,int R,int qL,int qR){
if(R<qL||qR<L) return 2e9;
if(qL<=L&&R<=qR) return Min[p];
int mid=(L+R)>>1;
return min(Query(ch[p][0],L,mid,qL,qR),Query(ch[p][1],mid+1,R,qL,qR));
}
int Query(int x,int y){
int res=2e9;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x,y);
res=min(res,Query(1,1,n+bcc,pos[top[x]],pos[x]));
x=pre[top[x]];
}
if(dep[x]<dep[y]) swap(x,y);
res=min(res,Query(1,1,n+bcc,pos[y],pos[x]));
if(y>n&&pre[y]) res=min(res,w[pre[y]]);
return res;
}
int main(){
freopen("uoj30.in","r",stdin);
freopen("uoj30.out","w",stdout);
scanf("%d%d%d",&n,&m,&Q);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
for(int i=1;i<=m;i++){
int x,y; scanf("%d%d",&x,&y);
add(x,y); add(y,x);
}
m=0; for(int i=1;i<=n;i++) if(!dfn[i]) Tarjan(i,0);
memset(fir,0,sizeof(fir)); tot=0;
//for(int i=1;i<=m;i++) printf("%d--%d\n",Es[i].x,Es[i].y);
for(int i=1;i<=m;i++) add(Es[i].x,Es[i].y), add(Es[i].y,Es[i].x);
dfs(1); Build_Chain(1,1);
for(int i=n+1;i<=n+bcc;i++) w[i]=*S[i].begin();
Build(1,n+bcc);
while(Q--){
char typ=getchar(); while(typ!='A'&&typ!='C') typ=getchar();
int x,y; scanf("%d%d",&x,&y);
if(typ=='A') printf("%d\n",Query(x,y));
else{
if(n<pre[x]){
S[pre[x]].erase(S[pre[x]].find(w[x]));
S[pre[x]].insert(y); w[pre[x]]=*S[pre[x]].begin();
Update(1,1,n+bcc,pos[pre[x]],w[pre[x]]);
}
Update(1,1,n+bcc,pos[x],w[x]=y);
}
}

return 0;
}