CF487E Tourists

#include<cstdio>
#include<cstring>
#include<iostream>
#include<set>
#include<vector>
#include<stack>
#define ri register int
#define N 405000
using namespace std;

int read() {
  int ret=0,f=0; char ch=getchar();
  while (ch<‘0‘ || ch>‘9‘) f|=(ch==‘-‘),ch=getchar();
  while (ch>=‘0‘ && ch<=‘9‘) ret=ret*10+(ch-‘0‘),ch=getchar();
  return f?-ret:ret;
}
int tn,n,m,q;
int w[N];

struct tree {
  vector<int> to[N];
  int fa[N],d[N],f[N][20];
  multiset<int> s[N];
  void add_edge(int u,int v) {
    to[u].push_back(v); 
        to[v].push_back(u);
  }
  void maketree(int x,int ff) {
    d[x]=d[ff]+1;
    f[x][0]=fa[x]=ff;
        for (ri i=1;i<=18;i++) f[x][i]=f[f[x][i-1]][i-1];
    for (ri i=0;i<to[x].size();i++) {
      int y=to[x][i];
      if (y==ff) continue;
      maketree(y,x);
    }
  }
  int lca(int u,int v) {
    if (d[u]<d[v]) swap(u,v);
    for (ri i=18;i>=0;i--) if (d[f[u][i]]>=d[v]) u=f[u][i];
    if (u==v) return u;
    for (ri i=18;i>=0;i--) if (f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];
    return fa[u];
  }
    void init(int x) {
      for (ri i=0;i<to[x].size();i++) {
          int y=to[x][i];
            if (y==fa[x]) continue;
            s[x].insert(w[y]);
        }
        w[x]=*(s[x].begin());
    }
} T;

struct link_cut_tree {
  bool rev[N];
  int fa[N],poi[N];
  int ch[N][2];
    
  inline bool notroot(int x) {
    return ch[fa[x]][0]==x || ch[fa[x]][1]==x;
  }
  inline bool opt(int x) {
    return (ch[fa[x]][1]==x);
  }
  void pushup(int x) {
    poi[x]=x;
    if (ch[x][0] && w[poi[ch[x][0]]]<w[poi[x]]) poi[x]=poi[ch[x][0]];
    if (ch[x][1] && w[poi[ch[x][1]]]<w[poi[x]]) poi[x]=poi[ch[x][1]];
  }
  void pushr(int x) {
    if (!rev[x] || !x) return;
    rev[x]=0;
    if (ch[x][0]) swap(ch[ch[x][0]][0],ch[ch[x][0]][1]),rev[ch[x][0]]^=1;
    if (ch[x][1]) swap(ch[ch[x][1]][0],ch[ch[x][1]][1]),rev[ch[x][1]]^=1;
  }

  void rotate(int x) {
    int y=fa[x],z=fa[y],s=opt(x),w=ch[x][1^s];
    fa[x]=z; if (notroot(y)) ch[z][opt(y)]=x;
    if (w) fa[w]=y; ch[y][s]=w;
    fa[y]=x; ch[x][1^s]=y;
    pushup(y); pushup(x);
  }

  void splay(int x) {
    int y=x;
    stack<int> stk; while (!stk.empty()) stk.pop();
    while (notroot(y)) stk.push(y),y=fa[y]; stk.push(y);
    while (!stk.empty()) pushr(stk.top()),stk.pop();
    while (notroot(x)) {
      int y=fa[x];
      if (!notroot(y)) rotate(x);
      else if (opt(x)==opt(y)) rotate(y),rotate(x); else rotate(x),rotate(x);
    }
  }

  void access(int x) {
    int y=0;
    while (x) {
      splay(x);
      ch[x][1]=y; pushup(x);
      y=x; x=fa[x];
    }
  }

  void makeroot(int x) {
    access(x); splay(x);
    rev[x]^=1;swap(ch[x][0],ch[x][1]);
    pushr(x);
  }

  void link(int u,int v) {
    makeroot(u);
    fa[u]=v;
  }
    
} lct;

struct graph {
  vector<int> to[N];
  stack<int> stk;
  int tot;
    int dfn[N],low[N];
  void add_edge(int u,int v) {
    to[u].push_back(v);
        to[v].push_back(u);
  }
  void tarjan(int x) {
    dfn[x]=low[x]=++tot;
        stk.push(x);
    for (ri i=0;i<to[x].size();i++) {
      int y=to[x][i];
      if (dfn[y]) {
        low[x]=min(low[x],dfn[y]);
      }
      else {
        tarjan(y);
        low[x]=min(low[y],low[x]);
        if (low[y]>=dfn[x]) {
          ++n; int t;
          do {
            t=stk.top(); stk.pop();
            T.add_edge(n,t);
          }
          while (t!=y);
          T.add_edge(n,x);
        }
      }
    }
  }
} G;

void change(int x,int v) {
    int y=T.fa[x];
    T.s[y].erase(w[x]);
    lct.splay(x);
    w[x]=v;
    T.s[y].insert(w[x]);
    lct.splay(y);
    w[y]=*(T.s[y].begin());
}

int query(int x,int y) {
    lct.makeroot(x);
    lct.access(y);
    lct.splay(y);
    int z=T.lca(x,y);
    if (z>tn) return min(w[lct.poi[y]],w[T.fa[z]]);
    return w[lct.poi[y]];
}

int main(){
    char opt[10];
  tn=n=read(); m=read(); q=read();
    memset(w,0x3f,sizeof(w));
  for (ri i=1;i<=n;i++) w[i]=read();
    for (ri i=1;i<=m;i++) {
      int u=read(),v=read();
        G.add_edge(u,v);
    }
    G.tot=0; G.tarjan(1);
    T.maketree(1,1);
    for (ri i=1;i<=n;i++) {
        lct.poi[i]=i;
        if (T.fa[i]!=i) lct.link(T.fa[i],i);
        if (i>tn) T.init(i);
    }
    for (ri i=1;i<=q;i++) {
      scanf("%s",opt);
        int u=read(),v=read();
        if (opt[0]==‘A‘) printf("%d\n",query(u,v));
        else if (opt[0]==‘C‘) change(u,v);
    }
    return 0;
}