测试地址：Tourists
题目大意：一个个点条边的无向连通图，每个点有点权，要求维护单点修改，还有若干次询问，每次询问两个点之间的简单路径上的点权最小值最小是多少。
做法：本题需要用到圆方树+multiset+树链剖分。
做过APIO2018-铁人两项的同学应该很快能看出来，我们实际上就是要找一个中间点，使得这个中间点的点权最小，而能作为中间点的点我们在上面那题讨论过了：路径所经过的所有点双中的点。因此我们把圆方树建出来，并把点双的信息用multiset存在方点中，然后求路径最小值就是一个裸的树链剖分了。
但是有一点要注意，如果是菊花图，那么单点修改可能会涉及到个点双，会爆，解决方法是每个点只对父亲方点有贡献，而在计算路径最小值时，如果LCA在方点上，再额外考虑它的父亲圆点即可。于是我们就以的时间复杂度解决了这一题。
（这题是十几天前写的，然而怎么都调不出来，今天发现我学了假的圆方树后赶紧改了一下，交了一发就过了……假圆方树毁一生啊……）
以下是本人代码：
#include <bits/stdc++.h>
using namespace std;
int n,m,q,w[200010];
int first[200010]={0},firstt[200010]={0},tot=0;
int tim=0,low[200010],dfn[200010],belong[200010]={0},totpbc;
int st[200010],top=0;
int fa[200010]={0},son[200010]={0},siz[200010],pos[200010],qpos[200010];
int tp[200010]={0},dep[200010]={0},seg[800010];
bool vis[200010]={0};
struct edge
{
int v,next;
}e[200010],t[200010];
multiset<int> s[200010];
multiset<int>::iterator it;
void insert(edge *e,int *first,int a,int b)
{
e[++tot].v=b;
e[tot].next=first[a];
first[a]=tot;
}
void init()
{
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 a,b;
scanf("%d%d",&a,&b);
insert(e,first,a,b);
insert(e,first,b,a);
}
totpbc=n;
}
void tarjan(int v,int fa)
{
vis[v]=1;
low[v]=dfn[v]=++tim;
st[++top]=v;
int now=top;
for(int i=first[v];i;i=e[i].next)
if (e[i].v!=fa)
{
if (!vis[e[i].v])
{
tarjan(e[i].v,v);
low[v]=min(low[v],low[e[i].v]);
if (low[e[i].v]>=dfn[v])
{
totpbc++;
insert(t,firstt,v,totpbc);
do
{
insert(t,firstt,totpbc,st[top]);
s[totpbc].insert(w[st[top]]);
belong[st[top]]=totpbc;
}while(st[top--]!=e[i].v);
w[totpbc]=*(s[totpbc].begin());
}
}
else low[v]=min(low[v],dfn[e[i].v]);
}
}
void dfs1(int v)
{
siz[v]=1;
int mxsiz=0;
for(int i=firstt[v];i;i=t[i].next)
{
fa[t[i].v]=v;
dep[t[i].v]=dep[v]+1;
dfs1(t[i].v);
if (siz[t[i].v]>mxsiz)
{
mxsiz=siz[t[i].v];
son[v]=t[i].v;
}
siz[v]+=siz[t[i].v];
}
}
void dfs2(int v,int top)
{
pos[v]=++tim;
qpos[tim]=v;
tp[v]=top;
if (son[v]) dfs2(son[v],top);
for(int i=firstt[v];i;i=t[i].next)
if (t[i].v!=son[v]) dfs2(t[i].v,t[i].v);
}
void buildtree(int no,int l,int r)
{
if (l==r)
{
seg[no]=w[qpos[l]];
return;
}
int mid=(l+r)>>1;
buildtree(no<<1,l,mid);
buildtree(no<<1|1,mid+1,r);
seg[no]=min(seg[no<<1],seg[no<<1|1]);
}
void segmodify(int no,int l,int r,int x,int d)
{
if (l==r)
{
seg[no]=d;
return;
}
int mid=(l+r)>>1;
if (x<=mid) segmodify(no<<1,l,mid,x,d);
else segmodify(no<<1|1,mid+1,r,x,d);
seg[no]=min(seg[no<<1],seg[no<<1|1]);
}
int segquery(int no,int l,int r,int s,int t)
{
if (l>=s&&r<=t) return seg[no];
int ret=1000000000,mid=(l+r)>>1;
if (s<=mid) ret=min(ret,segquery(no<<1,l,mid,s,t));
if (t>mid) ret=min(ret,segquery(no<<1|1,mid+1,r,s,t));
return ret;
}
void modify(int x,int y)
{
if (belong[x])
{
it=s[belong[x]].find(w[x]);
s[belong[x]].erase(it);
}
w[x]=y;
segmodify(1,1,totpbc,pos[x],y);
if (belong[x])
{
s[belong[x]].insert(w[x]);
w[belong[x]]=*(s[belong[x]].begin());
segmodify(1,1,totpbc,pos[belong[x]],w[belong[x]]);
}
}
int query(int x,int y)
{
int ret=1000000000;
while(tp[x]!=tp[y])
{
if (dep[tp[x]]<dep[tp[y]]) swap(x,y);
ret=min(ret,segquery(1,1,totpbc,pos[tp[x]],pos[x]));
x=fa[tp[x]];
}
if (dep[x]>dep[y]) swap(x,y);
ret=min(ret,segquery(1,1,totpbc,pos[x],pos[y]));
if (x>n&&fa[x]) ret=min(ret,w[fa[x]]);
return ret;
}
void work()
{
for(int i=1;i<=q;i++)
{
char s[3];
int x,y;
scanf("%s%d%d",s,&x,&y);
if (s[0]=='C') modify(x,y);
else printf("%d
",query(x,y));
}
}
int main()
{
init();
tot=0;
tarjan(1,0);
dfs1(1);
tim=0;
dfs2(1,1);
buildtree(1,1,totpbc);
work();
return 0;
}