题目链接

.

.

Solution

建圆方树，对于圆点权值直接就是点权，方点权值就是所有儿子的最小值，这个可以对于每个方点开一个\(multiset\)维护儿子点权。

那么直接上树剖就好了，注意如果\(lca\)是方点，那么他父亲的贡献也要算上。

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

#include
    
     using namespace std;void read(int &x) {    x=0;int f=1;char ch=getchar();    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;}void print(int x) {    if(x<0) putchar('-'),x=-x;    if(!x) return ;print(x/10),putchar(x%10+48);}void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}#define lf double#define ll long long #define ls p<<1#define rs p<<1|1#define mid ((l+r)>>1)#define iter multiset
     
       :: iterator const int maxn = 1e6+10;const int inf = 1e9;const lf eps = 1e-8;int n,m,val[maxn],cnt,rev[maxn];multiset
      
        s[maxn];struct Segment_Tree {    int t[maxn];    void update(int p) {t[p]=min(t[ls],t[rs]);}    void build(int p,int l,int r) {        if(l==r) return t[p]=val[rev[l]],void();        build(ls,l,mid),build(rs,mid+1,r),update(p);    }        void modify(int p,int l,int r,int x,int v) {        if(l==r) return t[p]=v,void();        if(x<=mid) modify(ls,l,mid,x,v);        else modify(rs,mid+1,r,x,v);        update(p);    }        int query(int p,int l,int r,int x,int y) {        if(x<=l&&r<=y) return t[p];        int res=1e9;        if(x<=mid) res=min(res,query(ls,l,mid,x,y));        if(y>mid) res=min(res,query(rs,mid+1,r,x,y));        return res;    }}SGT;struct Heavy_Light_Decomposation {      int head[maxn],tot,dfn[maxn],dfn_cnt,top[maxn],sz[maxn],dep[maxn],hs[maxn],fa[maxn];    struct edge{int to,nxt;}e[maxn<<1];    void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}    void ins(int u,int v) {add(u,v),add(v,u);}        void dfs1(int x,int Fa) {        fa[x]=Fa,dep[x]=dep[Fa]+1,sz[x]=1;        if(x>n) val[x]=*s[x].begin();        for(int v,i=head[x];i;i=e[i].nxt) {            if((v=e[i].to)==Fa) continue;            dfs1(v,x),sz[x]+=sz[v];            if(sz[hs[x]]
       
        dep[y]) swap(x,y);        if(x>n) ans=min(ans,val[fa[x]]);        ans=min(ans,SGT.query(1,1,cnt,dfn[x],dfn[y]));        return ans;    }}T;struct Graph {    int head[maxn],tot,dfn[maxn],low[maxn],sta[maxn],top,dfn_cnt;    struct edge{int to,nxt;}e[maxn<<1];    void add(int u,int v) {e[++tot]=(edge){v,head[u]},head[u]=tot;}    void ins(int u,int v) {add(u,v),add(v,u);}        void tarjan(int x,int fa) {        dfn[x]=low[x]=++dfn_cnt;sta[++top]=x;        for(int v,i=head[x];i;i=e[i].nxt) {            if((v=e[i].to)==fa) continue;            if(!dfn[v]) tarjan(v,x),low[x]=min(low[x],low[v]);            else {low[x]=min(low[x],dfn[v]);continue;}            if(low[v]>=dfn[x]) {                cnt++;T.ins(x,cnt);                while(top) {                    int now=sta[top--];T.ins(now,cnt);                    s[cnt].insert(val[now]);                    if(now==v) break;                }val[cnt]=*s[cnt].begin();            }        }    }}G;int main() {    int q;read(n),read(m),read(q);    for(int i=1;i<=n;i++) read(val[i]);    for(int i=1,x,y;i<=m;i++) read(x),read(y),G.ins(x,y);    cnt=n;G.tarjan(1,0);T.dfs1(1,0),T.dfs2(1);SGT.build(1,1,cnt);    for(int i=1;i<=q;i++) {        int x,y;char s[5];        scanf("%s",s+1);read(x),read(y);        if(s[1]=='A') write(T.query(x,y));        else T.modify(x,y);    }    return 0;}