codeforces_487E Tourists

题目:

  Cyberland 有 座城市,编号从 ,有 条双向道路连接这些城市。第 条路连接城市 。每天,都有成千上万的游客来到 Cyberland 游玩。
  在每一个城市,都有纪念品售卖,第 个城市售价为 。这个售价有时会变动。
  每一个游客的游览路径都有固定起始城市和终止城市,且不会经过重复的城市。
  他们会在路径上的城市中,售价最低的那个城市购买纪念品。
  你能求出每一个游客在所有合法的路径中能购买的最低售价是多少吗?
  你要处理 个操作:
  C a w: 表示 城市的纪念品售价变成
  A a b: 表示有一个游客要从 城市到 城市,你要回答在所有他的旅行路径中最低售价的最低可能值。

思路:

  一条路径的合法条件是不重复经过同一个城市,显然同一个点双分量中的点都能通过合法路线互达。对于每一个点双建一个新点与点双中的所有点相连(这就是圆方树?要不方便起见也叫圆点和方点好了),显然这样组成的还是一棵树,每个圆点的权值就是点双中的最小值。查询时直接求两点之间(在树上)的最小值即可。
  但是每次修改时,一个圆点可能与多个方点连接(菊花图就是 个),所以一个圆点修改时可能会引起 个方点的值修改。
  观察一棵圆方树,因为路径上也会有圆点,所以每个方点只维护所有儿子圆点的权值。如果路径 lca 为方点时在求一下父亲即可。这样每次修改就只要修改父亲了。(如下图)
        
  用树剖维护查询和修改,复杂度

代码:

#include <bits/stdc++.h>
#define rep(i, a, b) for(int i(a), i ##_END_(b); i <= i##_END_; i++) 
#define drep(i, a, b) for(int i(a), i ##_END_(b); i >= i##_END_; i--)
#define mset(a, b) memset(a, b, sizeof a)
using namespace std;
template<class T> inline bool tomax(T &a, T b) {return a < b ? a = b, 1 : 0;}
template<class T> inline bool tomin(T &a, T b) {return b < a ? a = b, 1 : 0;}
const int N = 1e5 + 5, M = 2e5 + 5;

template<int N, int M, class T> struct Link {
#define erep(k, G, o) for(int k = G.HEAD[o]; k; k = G.NXT[k])
    int HEAD[N], NXT[M], tot; T W[M];
    void clear() {tot = 0; mset(HEAD, 0);}
    void add(int x, T w) {NXT[++tot] = HEAD[x]; W[HEAD[x] = tot] = w;}
    T& operator[] (int x) {return W[x];}
};
Link<N, N * 2, int> G;
Link<M, M * 2, int> T;

template<class T>
struct DelHeap {
    priority_queue<T> h, d;
    void add(T x) {h.push(x);}
    void del(T x) {
        d.push(x);
        while(!d.empty() && d.top() == h.top()) 
            h.pop(), d.pop();
    }
    T top() {return h.top();}
};

int n, w[N];
namespace Graph{
    struct Edge {
        int u, v;
        bool operator!= (const Edge e) const {
            return u != e.u || v != e.v;
        }
    } stk[M];
    int dfn[N], low[N], cur, top, bcnt;
    int mark[N];
    void dfs(int o, int f) {
        dfn[o] = low[o] = ++cur;
        erep(k, G, o) {
            int v = G[k];
            if(v == f) continue;
            if(!dfn[v]) {
                stk[++top] = (Edge) {o, v};
                dfs(v, o);
                tomin(low[o], low[v]);
                if(low[v] >= dfn[o]) {
                    bcnt++;
                    do {
                        Edge e = stk[top];
                        if(mark[e.u] != bcnt) {
                            T.add(e.u, bcnt);
                            T.add(bcnt, e.u);
                            mark[e.u] = bcnt;
                        }
                        if(mark[e.v] != bcnt) {
                            T.add(e.v, bcnt);
                            T.add(bcnt, e.v);
                            mark[e.v] = bcnt;
                        }
                    } while(stk[top--] != (Edge) {o, v});
                }
            }
            else if(dfn[o] > dfn[v]) {
                tomin(low[o], dfn[v]);
                stk[++top] = (Edge) {o, v};
            }
        }
    }
    void init() {
        bcnt = n;
        dfs(1, 0);
    }
}

namespace Tree {
    int fa[M], hs[M], sz[M], dep[M];
    void dfs1(int o, int f) {
        dep[o] = dep[f] + 1; fa[o] = f;
        sz[o] = 1; hs[o] = 0;
        erep(k, T, o) {
            int v = T[k];
            if(v == f) continue;
            dfs1(v, o);
            sz[o] += sz[v];
            if(sz[v] > sz[hs[o]]) hs[o] = v;
        }
    }
    int dfn[M], tp[M], cur;
    void dfs2(int o, int f, int t) {
        tp[o] = t; dfn[o] = ++cur;
        if(hs[o]) dfs2(hs[o], o, t);
        erep(k, T, o) {
            int v = T[k];
            if(v == f || v == hs[o]) continue;
            dfs2(v, o, v);
        }
    }
    int seg[M << 2];
    DelHeap<int> hp[M];
#define ls (o << 1)
#define rs (o << 1 | 1)
#define mid ((L + R) >> 1)
#define lson ls, L, mid
#define rson rs, mid + 1, R
    void upd(int w, int x, bool f, int o, int L, int R) {
        if(L == R) {
            if(f) hp[w].add(-x);
            else hp[w].del(-x);
            seg[o] = -hp[w].top();
            return;
        }
        if(w <= mid) upd(w, x, f, lson);
        else upd(w, x, f, rson);
        seg[o] = min(seg[ls], seg[rs]);
    }
    int qry(int l, int r, int o, int L, int R) {
        if(l == L && r == R) return seg[o];
        if(r <= mid) return qry(l, r, lson);
        else if(l > mid) return qry(l, r, rson);
        else return min(qry(l, mid, lson), qry(mid + 1, r, rson));
    }
    int query(int u, int v) {
        int mn = 1e9, tot = Graph::bcnt;
        while(tp[u] != tp[v]) {
            if(dep[fa[tp[u]]] < dep[fa[tp[v]]]) swap(u, v);
            tomin(mn, qry(dfn[tp[u]], dfn[u], 1, 1, tot));
            u = fa[tp[u]];
        }
        if(dep[u] < dep[v]) swap(u, v);
        tomin(mn, qry(dfn[v], dfn[u], 1, 1, tot));
        if(fa[v] >= 1 && fa[v] <= n) tomin(mn, w[fa[v]]);
        return mn;
    }
    void change(int u, int x) {
        int tot = Graph::bcnt, f = fa[u];
        upd(dfn[u], w[u], false, 1, 1, tot);
        if(f) upd(dfn[f], w[u], false, 1, 1, tot);
        w[u] = x;
        upd(dfn[u], w[u], true, 1, 1, tot);
        if(f) upd(dfn[f], w[u], true, 1, 1, tot);
    }
    void init() {
        dfs1(1, 0); dfs2(1, 0, 1);
        int tot = Graph::bcnt;
        rep(i, 1, n) {
            int f = fa[i];
            upd(dfn[i], w[i], true, 1, 1, tot);
            if(f) upd(dfn[f], w[i], true, 1, 1, tot);
        }
    }
}

int main() {
    int m, q;
    scanf("%d%d%d", &n, &m, &q);
    rep(i, 1, n) scanf("%d", w + i);
    rep(i, 1, m) {
        int u, v;
        scanf("%d%d", &u, &v);
        G.add(u, v); G.add(v, u);
    }
    Graph::init(); 
    Tree::init();
    while(q--) {
        char c;
        do c = getchar(); while(c != 'C' && c != 'A');
        int u, v;
        scanf("%d%d", &u, &v);
        if(c == 'A') printf("%d\n", Tree::query(u, v));
        else Tree::change(u, v);
    }
    return 0;
}