题目大意
给定一个
N
个点M条边的无向图，每个点有一个点权。现在有两种操作，第一种是修改一个点的点权，第二种是询问两点间路径上的最小点权（不能经过重复的点）。操作数为
Q
。
N,M,Q≤109
解题思路
我们先考虑没有修改点权的情况。那么我们可以先用点双连通分量缩环，缩环后的点权为环上的最小值。而每组询问就变成了求树上两点间的最权值。这个经典问题可以用倍增后链剖来维护。
但是有修改点权时这个方法就行不通了，因为一个点可能存在与多个联通块，特别是菊花图的情况复杂度就会到
N2
级别。那么我们考虑另一种建树的方式，对于一个联通块，我们需要特殊考虑的就只有割点，那么我们可这样建树：对于每个点双我们新增加一个节点，里面存的是这个点双中最小的权值，对于在Dfs序不是最小的点都向这个点连一条边。而对于Dfs序最小的点，我们让新增的点向它连一条边（姑且称为特殊点）。而我们修改一个点时，把代表它所在点双的新增点也更新。而现在的问题是我们对于一个割点，不能修改所有它所处的点双，那么我们讨论一下这些点上与它在树上的关系： 1. 他的父亲：因为父亲只有一个，并且一定是代表一个点双的点，那么直接把他的权值更新就好了。 2. 他的儿子：对于它的儿子可能有很多，我们不能一一去修改，但是我们可以发现，对于每次询问到这个点儿子代表的点双时只有两种情况，一个就是
Lca
在这个这个点双代表点的上方，那么也肯定会经过我们修改修改的点。否则
Lca
肯定就是这个点双的代表点，那么除了查询路径上的值，再查询一下这和点双代表点的父亲就可以了。
这样的话每次修改就只用修改两个点，每次查询最多只会查询一条路径加上一个点，那么复杂度就变成了
O（Qlog2N）
。注意由于有了修改操作所以不能用倍增维护。
程序
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
const int MAXN =
2e5 +
5;
const int Inf =
1e9 +
7;
multiset<int> S[MAXN];
vector<int> R[MAXN];
int N, M, Q, Val[MAXN], Tr[MAXN *
4];
int tot, Last[MAXN], Next[MAXN *
2], Go[MAXN *
2];
int top, time, Cnt, Low[MAXN], Dfn[MAXN], D[MAXN], Bel[MAXN];
int Deep[MAXN], Pre[MAXN], Size[MAXN], MSon[MAXN], Top[MAXN], Ord[MAXN];
void Link(
int u,
int v) {
Next[++ tot] = Last[u], Last[u] = tot, Go[tot] = v;
}
void Tarjan(
int Now,
int Pre) {
Dfn[Now] = Low[Now] = ++ time;
D[++ top] = Now;
for (
int i =
0; i < R[Now].size(); i ++) {
int v = R[Now][i];
if (!Dfn[v]) {
Tarjan(v, Now);
Low[Now] = min(Low[Now], Low[v]);
if (Low[v] >= Dfn[Now]) {
++ Cnt;
while (
1 ==
1) {
int t = D[top --];
Bel[t] = Cnt;
S[Cnt].insert(Val[t]);
Link(Cnt, t);
if (t == v)
break;
}
Link(Now, Cnt);
}
}
else if (v != Pre) Low[Now] = min(Low[Now], Dfn[v]);
}
}
void Modify(
int Now,
int l,
int r,
int Side,
int Val) {
if (l == r) {
Tr[Now] = Val;
return;
}
int Mid = (l + r) >>
1;
if (Side <= Mid) Modify(Now *
2, l, Mid, Side, Val);
else
Modify(Now *
2 +
1, Mid +
1, r, Side, Val);
Tr[Now] = min(Tr[Now *
2], Tr[Now *
2 +
1]);
}
void Modify(
int Side,
int V) {
if (Bel[Side]) {
int Now = Bel[Side];
S[Now].erase(S[Now].find(Val[Side]));
S[Now].insert(V);
Modify(
1,
1, time, Ord[Now], *S[Now].begin());
}
Val[Side] = V;
Modify(
1,
1, time, Ord[Side], V);
}
int Query(
int Now,
int l,
int r,
int lx,
int rx) {
if (l == lx && r == rx)
return Tr[Now];
int Mid = (l + r) >>
1;
if (rx <= Mid)
return Query(Now *
2, l, Mid, lx, rx);
else
if (lx > Mid)
return Query(Now *
2 +
1, Mid +
1, r, lx, rx);
else
return min(Query(Now *
2, l, Mid, lx, Mid), Query(Now *
2 +
1, Mid +
1, r, Mid +
1, rx));
}
int Query(
int u,
int v) {
int Num = Inf;
while (Top[u] != Top[v]) {
if (Deep[Top[u]] < Deep[Top[v]]) swap(u, v);
Num = min(Num, Query(
1,
1, time, Ord[Top[u]], Ord[u]));
u = Pre[Top[u]];
}
if (Deep[u] < Deep[v]) swap(u, v);
Num = min(Num, Query(
1,
1, time, Ord[v], Ord[u]));
if (v > N && Pre[v]) Num = min(Num, Val[Pre[v]]);
return Num;
}
void Basis(
int Now,
int Fa) {
Size[Now] =
1, Pre[Now] = Fa, Deep[Now] = Deep[Fa] +
1;
for (
int p = Last[Now]; p; p = Next[p]) {
int v = Go[p];
if (v == Fa)
continue;
Basis(v, Now);
Size[Now] += Size[v];
if (Size[v] > Size[MSon[Now]]) MSon[Now] = v;
}
}
void Promote(
int Now,
int top) {
if (!Now)
return;
Ord[Now] = ++ time, Top[Now] = top;
Promote(MSon[Now], top);
for (
int p = Last[Now]; p; p = Next[p]) {
int v = Go[p];
if (v == MSon[Now] || v == Pre[Now])
continue;
Promote(v, v);
}
}
void Prepare() {
Cnt = N;
Tarjan(
1,
0);
time =
0;
Basis(
1,
0), Promote(
1,
1);
for (
int i =
1; i <= time; i ++) {
if (i <= N) Modify(
1,
1, time, Ord[i], Val[i]);
else
Modify(
1,
1, time, Ord[i], *S[i].begin());
}
}
void Solve() {
for (
int i =
1; i <= Q; i ++) {
char ch;
scanf(
"\n%c", &ch);
if (ch ==
'C') {
int Side, Val;
scanf(
"%d%d", &Side, &Val);
Modify(Side, Val);
}
else {
int u, v;
scanf(
"%d%d", &u, &v);
printf(
"%d\n", Query(u, v));
}
}
}
int main() {
scanf(
"%d%d%d", &N, &M, &Q);
for (
int i =
1; i <= N; i ++)
scanf(
"%d", &Val[i]);
for (
int i =
1; i <= M; i ++) {
int u, v;
scanf(
"%d%d", &u, &v);
R[u].push_back(v);
R[v].push_back(u);
}
Prepare();
Solve();
}
