「Codeforces #487E」Tourists

Codeforces #487E

题意

给你一张 \(n\) 个点 \(m\) 条边的无向图,每个点有点权,\(q\) 次操作

  1. C a w,将第 \(a\) 个点的权值改为 \(w\)

  2. A a b,询问 \(a\)\(b\) 所有可能的简单路径上的点权最小值

简单路径即不经过一个点超过一次的路径

\(n,m,q\le 10^5\)


做法

建圆方树,每个方点维护一个可以删除的小根堆,保存圆方树上这个方点所有儿子的权值

考虑两个点路径上的点权最小值就是在圆方树上路径经过的所有方点的堆顶的最小值和LCA位置的特判

  1. 若LCA是方点,这时LCA所在的点双的深度最小点并没有被计算到,即LCA的树上父亲,判一下即可

  2. 若LCA是圆点,这时LCA本身没有被计算到,判一下即可

用树剖维护链上最小值

每次修改只要在一个堆中删除和插入各一次

总复杂度 \(\mathcal O(n\log^2n)\)


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<queue>

using namespace std;
#define ll long long

inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s==t?t=(s=buf)+fread(buf,1,IN_LEN,stdin),(s==t?-1:*s++):*s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig=false, c=read(); !isdigit(c); c=read()) {
if (c == '-') iosig=true;
if (c == -1) return;
}
for (x=0; isdigit(c); c=read()) x=((x+(x<<2))<<1)+(c^'0');
if (iosig) x=-x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh=obuf;
inline void print(char c) {
if (ooh==obuf+OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh=obuf;
*ooh++=c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x==0) print('0');
else {
if (x<0) print('-'), x=-x;
for (cnt=0; x; x/=10) buf[++cnt]=x%10+48;
while(cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }

const int N = 100005, inf = 1e9;
int n, m, q, num, cnt, stop, p, low[N], stk[N], w[N], h[N], siz[N<<1], top[N<<1], e[N<<1], pre[N<<1], dfn[N<<1], fa[N<<1], b[N<<1], dep[N<<1], s[N<<3];
vector<int> a[N<<1];
struct heap{
priority_queue<int, vector<int>, greater<int>> a, b;
inline void push(int x){ a.push(x);}
inline void erase(int x){ b.push(x);}
inline int top(){
while(b.size() && a.top()==b.top()) a.pop(), b.pop();
return a.top();
}
} f[N];
inline void add(int x, int y){ e[++num]=y, pre[num]=h[x], h[x]=num;}
void tarjan(int u){
dfn[u]=low[u]=++cnt;
stk[++stop]=u;
for(int i=h[u]; i; i=pre[i]) if(e[i]!=fa[u]){
if(!dfn[e[i]]){
tarjan(e[i]), low[u]=min(low[u], low[e[i]]);
if(low[e[i]]>=dfn[u]){
++p;
a[u].push_back(p);
do
a[p].push_back(stk[stop]), f[p-n].push(w[stk[stop]]);
while(stk[stop--]!=e[i]);
}
}
else low[u]=min(low[u], dfn[e[i]]);
}
}
void dfs1(int u){
siz[u]=1;
for(int v:a[u]) fa[v]=u, dep[v]=dep[u]+1, dfs1(v), siz[u]+=siz[v];
}
void dfs2(int u){
dfn[u]=++cnt, b[dfn[u]]=(u>n?f[u-n].top():inf);
int son=0;
for(int v:a[u]) if(siz[v]>siz[son]) son=v;
if(son) top[son]=top[u], dfs2(son);
for(int v:a[u]) if(v!=son) top[v]=v, dfs2(v);
}
void build(int l, int r, int t){
if(l==r) return (void)(s[t]=b[l]);
int mid=(l+r)/2, k=t<<1;
build(l, mid, k), build(mid+1, r, k|1);
s[t]=min(s[k], s[k|1]);
}
void modify(int l, int r, int t, int x, int y){
if(l==r) return (void)(s[t]=y);
int mid=(l+r)/2, k=t<<1;
if(x<=mid) modify(l, mid, k, x, y); else modify(mid+1, r, k|1, x, y);
s[t]=min(s[k], s[k|1]);
}
int query(int l, int r, int t, int L, int R){
if(L<=l && r<=R) return s[t];
int mid=(l+r)/2, k=t<<1;
return min(L<=mid?query(l, mid, k, L, R):inf, R>mid?query(mid+1, r, k|1, L, R):inf);
}
int main() {
read(n), read(m), read(q), p=n;
for(int i=1; i<=n; ++i) read(w[i]);
for(int i=1, x, y; i<=m; ++i) read(x), read(y), add(x, y), add(y, x);
tarjan(1);
dfs1(1), top[1]=1, cnt=0, dfs2(1);
build(1, p, 1);
while(q--){
static char opt;
static int x, y;
while(isspace(opt=read()));
read(x), read(y);
if(opt=='C'){
if(x!=1){
f[fa[x]-n].erase(w[x]), f[fa[x]-n].push(y);
modify(1, p, 1, dfn[fa[x]], f[fa[x]-n].top());
}
w[x]=y;
}
else{
int ans=inf;
while(top[x]!=top[y]){
if(dep[top[x]]<dep[top[y]]) swap(x, y);
ans=min(ans, query(1, p, 1, dfn[top[x]], dfn[x]));
x=fa[top[x]];
}
if(dep[x]>dep[y]) swap(x, y);
ans=min(ans, query(1, p, 1, dfn[x], dfn[y]));
print(min(ans, x>n?w[fa[x]]:w[x])), print('\n');
}
}
return flush(), 0;
}