CF487E Tourists 做题记录
码农题，写线段树给我写爽了，这道题又是图，但是要求路径最小值，所以还是最好要转化成树，所以使用圆方树，而且点双在这道题有很好的性质：方点的点权就是这个点双的最小值，因为点双内两点肯定能够经过第三个点。
所以我们先建好圆方树，敲好树剖，如果没有修改的话，用线段树维护方点代表点双的最小值，再用线段树维护整棵树区间最小值，然后树剖求就可以了。但~~是，有修改就不好做了，话说没修可以用点权重构二叉树吗？
如果修改把该圆点与所有相连的方点全部修改，那我用个菊花图你不就炸了吗，所以这里有个恶作剧：每个方点只统计作为它儿子的点双的点权，而有可能为它父亲的点双的点就不管，这样每次修改只需要修改一个方点，而最后统计答案是如果 LCA 是方点，那再统计它的父亲，即那个本应被统计却没被统计的圆点。题解里面一堆用 multiset 维护方点最小值的，这里用的是动态开点线段树，码量多了不止一倍，不过好写爱写😋
另外记得修改时修改维护整棵线段树时用时间戳表示线段树下标，维护方点最小值用一个数组记录该圆点是第几位下标，其他就没什么了。
//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 500005
#define M 1000000007
using namespace std;
inline ll read()
{
ll x = 0, f = 1;
char ch = gr();
while (ch < '0' || ch > '9')
ch == '-' ? f = -1, ch = gr() : ch = gr();
while (ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
return x * f;
}
inline void write(ll x)
{
static int sta[39], top = 0;
if (x < 0)
pr('-'), x = -x;
do
sta[++top] = x % 10, x /= 10;
while (x);
while (top)
pr(sta[top--] ^ 48);
}
struct Edge
{
struct edge
{
int v, next;
} e[N << 1];
int head[N], cnt;
inline void tdd(int u, int v)
{
e[++cnt] = {v, head[u]}, head[u] = cnt;
e[++cnt] = {u, head[v]}, head[v] = cnt;
}
} g, t;
int n, m, q, u, v, bcc, cnt, tp;
int dfn[N], low[N], stack[N];
int a[N], w[N], fa[N], sz[N], num[N], pos[N], top[N], bson[N], deep[N], root[N];
void tarjan(int u)
{
dfn[u] = low[u] = ++cnt;
stack[++tp] = u;
for (rnt i = g.head[u]; i; i = g.e[i].next)
{
int v = g.e[i].v;
if (!dfn[v])
{
tarjan(v), low[u] = min(low[v], low[u]);
if (low[v] == dfn[u])
{
bcc++;
while (stack[tp + 1] != v)
t.tdd(stack[tp--], bcc);
t.tdd(u, bcc);
}
}
else
low[u] = min(low[u], dfn[v]);
}
}
void dfs1(int u, int f)
{
fa[u] = f, sz[u] = 1;
deep[u] = deep[f] + 1;
for (rnt i = t.head[u]; i; i = t.e[i].next)
{
int v = t.e[i].v;
if (v == f)
continue;
dfs1(v, u);
sz[u] += sz[v];
if (sz[v] > sz[bson[u]])
bson[u] = v;
}
}
void dfs2(int u, int tp)
{
top[u] = tp;
dfn[u] = ++cnt;
w[cnt] = a[u];
if (!bson[u])
return;
dfs2(bson[u], tp);
for (rnt i = t.head[u]; i; i = t.e[i].next)
{
int v = t.e[i].v;
if (v == fa[u] || v == bson[u])
continue;
dfs2(v, v);
}
}
struct tree
{
int l, r, min;
} s[N << 2];
void push_up(int u)
{
s[u].min = M;
if (s[u << 1].min)
s[u].min = min(s[u << 1].min, s[u].min);
if (s[u << 1 | 1].min)
s[u].min = min(s[u << 1 | 1].min, s[u].min);
}
void build(int u, int l, int r)
{
s[u].l = l, s[u].r = r;
if (l == r)
return s[u].min = w[l], void();
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
push_up(u);
}
void modify(int u, int x, int w)
{
if (s[u].l == s[u].r)
return s[u].min = w, void();
int mid = (s[u].l + s[u].r) >> 1;
if (x <= mid)
modify(u << 1, x, w);
else
modify(u << 1 | 1, x, w);
push_up(u);
}
int query(int u, int l, int r)
{
if (l <= s[u].l && s[u].r <= r)
return s[u].min;
int mid = (s[u].l + s[u].r) >> 1, ans = M;
if (l <= mid)
ans = min(ans, query(u << 1, l, r));
if (r >= mid + 1)
ans = min(ans, query(u << 1 | 1, l, r));
return ans;
}
struct tree2
{
int lc, rc, min;
} k[N << 2];
void push_upk(int u)
{
k[u].min = M;
if (k[k[u].lc].min)
k[u].min = min(k[k[u].lc].min, k[u].min);
if (k[k[u].rc].min)
k[u].min = min(k[k[u].rc].min, k[u].min);
}
void modifyk(int &u, int l, int r, int x, int w)
{
if (!u)
u = ++cnt;
if (l == r)
return k[u].min = w, void();
int mid = (l + r) >> 1;
if (x <= mid)
modifyk(k[u].lc, l, mid, x, w);
else
modifyk(k[u].rc, mid + 1, r, x, w);
push_upk(u);
}
int get_lca(int a, int b)
{
int ans = M;
while (top[a] != top[b])
{
if (deep[top[a]] < deep[top[b]])
swap(a, b);
ans = min(ans, query(1, dfn[top[a]], dfn[a]));
a = fa[top[a]];
}
if (deep[a] > deep[b])
swap(a, b);
ans = min(ans, query(1, dfn[a], dfn[b]));
if (a > n)
ans = min(ans, w[dfn[fa[a]]]);
return ans;
}
int main()
{
char ch;
bcc = n = read(), m = read(), q = read();
for (rnt i = 1; i <= n; i++)
a[i] = read();
for (rnt i = 1; i <= m; i++)
u = read(), v = read(), g.tdd(u, v);
tarjan(1), cnt = 0, dfs1(1, 0), dfs2(1, 1);
cnt = 0;
for (rnt i = 1; i <= n; i++)
if (fa[i])
modifyk(root[fa[i]], 1, bcc, ++num[fa[i]], a[i]), pos[i] = num[fa[i]];
for (rnt i = n + 1; i <= bcc; i++)
w[dfn[i]] = k[root[i]].min;
build(1, 1, bcc);
for (rnt i = 1; i <= q; i++)
{
cin >> ch, u = read(), v = read();
if (ch == 'A')
write(get_lca(u, v)), pr(10);
else
{
modify(1, dfn[u], v);
if (fa[u])
{
modifyk(root[fa[u]], 1, bcc, pos[u], v);
modify(1, dfn[fa[u]], k[root[fa[u]]].min);
}
w[dfn[u]] = v;
}
}
return 0;
}