[Codeforces] E. Tourists

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : E. Tourists
Source            : Codeforces
Category          : Graph Theory
Algorithm         : Block Cut Tree, Heavy Light Decomposition, Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
#define em             emplace
#define eb             emplace_back
#define sz(a)          a.size()
#define vi             vector <int>
 
inline int read()      { int a; scanf("%d", &a); return a; }
 
static const int maxn = 2e5 + 5;
static const int logn = 19;
 
vi graph[maxn], btree[maxn];
stack <int> s;
multiset <int> ord[maxn];
int tnode, tedge, tquery;
int dfsTime, disc[maxn], low[maxn], tot, bcc[maxn], w[maxn];
 
void addEdge1(int u, int v)
{
    graph[u].eb(v);
    graph[v].eb(u);
}
 
void addEdge2(int u, int v)
{
    btree[u].eb(v);
    btree[v].eb(u);
}
 
void findBCC(int u = 1, int p = -1)
{
    dfsTime++;
    disc[u] = low[u] = dfsTime;
    s.emplace(u);
    for (int v : graph[u])
    {
        if (v == p) continue;
        if (!disc[v])
        {
            findBCC(v, u);
            low[u] = min(low[u], low[v]);
            if (disc[u] <= low[v])
            {
                tot++;
                int h;
                do {
                    h = s.top();
                    addEdge2(h, tot);
                    bcc[h] = tot;
                    ord[tot].em(w[h]);
                    s.pop();
                } while (h != v);
                addEdge2(tot, u);
            }
        }
        else
        {
            low[u] = min(low[u], disc[v]);
        }
    }
}
 
int subTreeSize[maxn], father[maxn][logn], depth[maxn];
 
void dfs(int u = 1, int p = -1)
{
    for (int i = 1; i < logn; i++) father[u][i] = father[ father[u][i-1] ][i-1];
    subTreeSize[u] = 1;
    for (int v : btree[u])
    {
        if (v == p) continue;
        depth[v] = depth[u] + 1;
        father[v][0] = u;
        dfs(v, u);
        subTreeSize[u] += subTreeSize[v];
    }
}
 
int findLCA(int u, int v)
{
    if (depth[u] < depth[v]) swap(u, v);
    for (int i = logn-1; i >= 0; i--) if (depth[ father[u][i] ] >= depth[v]) u = father[u][i];
    if (u == v) return u;
    for (int i = logn-1; i >= 0; i--) if (father[u][i] != father[v][i]) u = father[u][i], v = father[v][i];
    return father[u][0];
}
 
int chainNo, chainHead[maxn], chainInd[maxn], chainPos[maxn], chainSize[maxn],
    baseArray[maxn], posBase[maxn], ptr, S, E;
 
void hld(int u = 1, int p = -1)
{
    if (chainHead[chainNo] == -1) chainHead[chainNo] = u;
    chainInd[u] = chainNo;
    ptr++;
    baseArray[ptr] = w[u];
    posBase[u] = ptr;
    int specialChild = -1;
    int maxSize = -1;
    for (int v : btree[u])
    {
        if (v == p) continue;
        if (subTreeSize[v] > maxSize) maxSize = subTreeSize[v], specialChild = v;
    }
    if (specialChild != -1) hld(specialChild, u);
    for (int v : btree[u])
    {
        if (v == p) continue;
        if (v != specialChild) chainNo++, hld(v, u);
    }
}
 
struct segmentTree
{
    int minValue;
    void assignLeaf(int val)
    {
        minValue = val;
    }
    void marge(segmentTree &l, segmentTree &r)
    {
        if (l.minValue == -1) minValue = r.minValue;
        else if (r.minValue == -1) minValue = l.minValue;
        else minValue = min(l.minValue, r.minValue);
    }
    int getRes()
    {
        return minValue;
    }
} TREE[maxn << 2];
 
void update(int node, int a, int b, int pos, int value)
{
    if (a > b || a > pos || b < pos) return;
    if (a >= pos && b <= pos)
    {
        TREE[node].assignLeaf(value);
        return;
    }
    int left = node << 1;
    int right = left | 1;
    int mid = (a + b) >> 1;
    update(left, a, mid, pos, value);
    update(right, mid+1, b, pos, value);
    TREE[node].marge(TREE[left], TREE[right]);
}
 
segmentTree query(int node, int a, int b, int i, int j)
{
    if (a > b || a > j || b < i) return {-1};
    if (a >= i && b <= j) return TREE[node];
    int left = node << 1;
    int right = left | 1;
    int mid = (a + b) >> 1;
    segmentTree p1, p2, res;
    p1 = query(left, a, mid, i, j);
    p2 = query(right, mid+1, b, i, j);
    res.marge(p1, p2);
    return res;
}
 
void changeNodeCost(int u, int value)
{
    int pos = posBase[u];
    update(1, S, E, pos, value);
}
 
int queryUp(int u, int v)
{
    // u -> always the lowest node, v -> lca
    int uChain, vChain = chainInd[v], minValue = INT_MAX;
    while (true)
    {
        uChain = chainInd[u];
        if (uChain == vChain)
        {
            int l = posBase[v];
            int r = posBase[u];
            if (l > r) break;
            int ans = query(1, S, E, l, r).getRes();
            if (ans < minValue) minValue = ans;
            break;
        }
        int l = posBase[ chainHead[uChain] ];
        int r = posBase[u];
        int ans = query(1, S, E, l, r).getRes();
        if (ans < minValue) minValue = ans;
        u = father[ chainHead[uChain] ][0];
    }
    return minValue;
}
 
int queryHLD(int u, int v)
{
    int lca = findLCA(u, v); // ok
    int minValue = queryUp(u, lca);
    minValue = min(minValue, queryUp(v, lca));
    if (lca > tnode) minValue = min(minValue, queryUp(lca, father[lca][0]));
    return minValue;
}
 
void init()
{
    ptr = 0;
    chainNo = 0;
    for (int i = 0; i < maxn; i++)
    {
        graph[i].clear();
        btree[i].clear();
        bcc[i] = 0;
        subTreeSize[i] = 0;
        chainHead[i] = -1;
        chainInd[i] = 0;
        depth[i] = 0;
        baseArray[i] = 0;
        posBase[i] = 0;
        bcc[i] = 0;
        for (int j = 0; j < logn; j++) father[i][j] = 0;
    }
}
 
int main()
{
//    freopen("in.txt", "r", stdin);
 
    init();
    tnode = read(), tedge = read(), tquery = read();
    for (int i = 1; i <= tnode; i++) w[i] = read();
    for (int e = 1; e <= tedge; e++)
    {
        int u = read(), v = read();
        addEdge1(u, v);
    }
    tot = tnode; // must
    findBCC();
    depth[1] = 1;
    dfs();
    hld();
    S = 1;
    E = ptr;
    for (int i = 1; i <= tnode; i++) changeNodeCost(i, w[i]);
    for (int i = tnode+1; i <= tot; i++) changeNodeCost(i, *ord[i].begin());
    char t;
    while (tquery--)
    {
        int u, v;
        scanf("\n%c %d %d", &t, &u, &v);
        if (t == 'C')
        {
            changeNodeCost(u, v);
            if (bcc[u])
            {
                int bccno = bcc[u];
                ord[bccno].erase(ord[bccno].find(w[u]));
                ord[bccno].em(v);
                changeNodeCost(bccno, *ord[bccno].begin());
            }
            w[u] = v;
        }
        else printf("%d\n", queryHLD(u, v));
    }
}