```cpp
#ifndef _GLIBCXX_NO_ASSERT
#include <cassert>
#endif
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#if __cplusplus >= 201103L
#include <ccomplex>
#include <cfenv>
#include <cinttypes>
#include <cstdalign>
#include <cstdbool>
#include <cstdint>
#include <ctgmath>
#include <cuchar>
#include <cwchar>
#include <cwctype>
#endif
// C++
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <codecvt>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#if __cplusplus >= 201402L
#include <shared_mutex>
#endif
#define maxn 200010
#define maxm 800010
#define size siz
#define inf 0x3f3f3f3f
using namespace std;
struct node
{
int v, nxt;
};
struct G
{
node edge[maxm];
int k, head[maxn];
inline void add(int u, int v)
{
edge[++k] = (node){v, head[u]};
head[u] = k;
}
} tree, gph;
struct ST
{
int tr[maxm];
void ______(int id, int l, int r, int p, int val)
{
if (l == r)
{
tr[id] = val;
return;
}
int mid = (l + r) >> 1;
if (p <= mid)
______(id << 1, l, mid, p, val);
else
______(id << 1 | 1, mid + 1, r, p, val);
tr[id] = min(tr[id << 1], tr[id << 1 | 1]);
}
int ____________(int id, int l, int r, int L, int R)
{
if (l >= L && r <= R)
{
return tr[id];
}
int res = inf, mid = (l + r) >> 1;
if (L <= mid)
res = min(res, ____________(id << 1, l, mid, L, R));
if (R > mid)
res = min(res, ____________(id << 1 | 1, mid + 1, r, L, R));
return res;
}
} st;
int n, m, q;
int a[maxn];
int cube;
int dfn[maxn], low[maxn], t;
stack<int> s;
void tarjan(int u)
{
low[u] = dfn[u] = ++t;
s.push(u);
for (register int _ = gph.head[u], v; _; _ = gph.edge[_].nxt)
{
v = gph.edge[_].v;
if (!dfn[v])
{
tarjan(v);
low[u] = min(low[v], low[u]);
if (low[v] >= dfn[u])
{
tree.add(++cube, u);
tree.add(u, cube);
int x;
do
{
x = s.top();
s.pop();
tree.add(cube, x);
} while (x != v);
}
}
else
low[u] = min(low[u], dfn[v]);
}
}
int son[maxn], siz[maxn], top[maxn], dep[maxn], fa[maxn];
int pos[maxn], tid[maxn], tim;
multiset<int> __[maxn];
void dfs1(int u, int dad)
{
fa[u] = dad;
dep[u] = dep[dad] + 1;
siz[u] = 1;
if (u <= n && dad)
__[dad].insert(a[u]);
for (register int _ = tree.head[u], v; _; _ = tree.edge[_].nxt)
{
v = tree.edge[_].v;
if (v == dad)
continue;
dfs1(v, u);
size[u] += size[v];
if (size[v] > size[son[u]] || !son[u])
son[u] = v;
}
}
void dfs2(int u, int tp)
{
top[u] = tp;
pos[u] = ++tim;
tid[u] = u;
if (son[u])
dfs2(son[u], tp);
for (register int _ = tree.head[u], v; _; _ = tree.edge[_].nxt)
{
v = tree.edge[_].v;
if (v != fa[u] && v != son[u])
dfs2(v, v);
}
}
int ____________(int u, int v)
{
int res = inf;
while (top[u] ^ top[v])
{
if (dep[top[u]] < dep[top[v]])
swap(u, v);
res = min(res, st.____________(1, 1, cube, pos[top[u]], pos[u]));
u = fa[top[u]];
}
if (dep[u] > dep[v])
swap(u, v);
res = min(res, st.____________(1, 1, cube, pos[u], pos[v]));
if (u <= n)
return res;
else
return min(res, a[fa[u]]);
}
void ______(int id, int val)
{
if (fa[id])
{
__[fa[id]].erase(__[fa[id]].find(a[id]));
__[fa[id]].insert(val);
st.______(1, 1, cube, pos[fa[id]], *__[fa[id]].begin());
}
a[id] = val;
st.______(1, 1, cube, pos[id], val);
}
int main()
{
scanf("%d%d", &n, &m);
scanf("%d", &q);
a[0] = inf;
register int _;
int u, v;
for (_ = 1; _ <= n; _++)
scanf("%d", &a[_]);
for (_ = 1; _ <= m; _++)
scanf("%d%d", &u, &v), gph.add(u, v), gph.add(v, u);
cube = n;
tarjan(1);
dfs1(1, 0);
dfs2(1, 1);
for (_ = 1; _ <= n; _++)
st.______(1, 1, cube, pos[_], a[_]);
for (_ = n + 1; _ <= cube; _++)
st.______(1, 1, cube, pos[_], *__[_].begin());
char opt;
while (q--)
{
cin >> opt; //高级无效字符过滤器（大雾
scanf("%d%d", &u, &v);
switch (opt)
{
case 'A':
{
printf("%d\n", ____________(u, v));
break;
}
case 'C':
{
______(u, v);
break;
}
case 'Q':
{
printf("%d\n", a[u] - ____________(u, v));
}
default:
break;
}
}
return 0;
}
```
by 镉八君 @ 2018-10-17 11:23:29
@[lovelausanneforever](/space/show?uid=61644)
by 镉八君 @ 2018-10-17 11:24:34
+1
by lukelin @ 2018-10-17 11:28:28
CF紫色以上的题目好像都有这问题
by lukelin @ 2018-10-17 11:28:56
@[lukelin](/space/show?uid=20462) 怪不得是道黑题，主要是提交比较困难（大雾
by 镉八君 @ 2018-10-17 11:31:13
自觉滚到CF然后过了QWQ
（心疼在Luogu的AC
by 镉八君 @ 2018-10-17 11:40:31
佩服你的毅力
by Martin6666 @ 2018-10-17 11:53:42
然而并没有啊……
表示你站的remotejudge一点用没有……
by shadowice1984 @ 2018-10-17 13:45:00
不好意思打错了
是一点锅没有
by shadowice1984 @ 2018-10-17 13:45:36
@[镉八君](/space/show?uid=61653) 因为你菜啊QWQ
by 夢·壹生所愛 @ 2018-10-17 14:31:31