Codeforces Round #673 (Div. 1) D. Graph and Queries (R2600)

いろんな方法がありそう。Union-Find のマージ過程を表す木でやったけど、ほかにも Undo 付き Union-Find を使うなど

• 問題へのリンク

問題概要

頂点数 、辺数 のグラフが与えられる。初期状態では各頂点に という値がついている (すべて 1 以上で disjoint)。以下の 2 タイプのクエリに 回答えよ。

• type 1：頂点 を含む連結成分内で、 の値の最大値を求めよ。さらに最大となった箇所の 値を 0 で書き換えておく
• type 2：辺 を削除する

制約

• 
• 
• 

考えたこと

一般に、グラフの辺削除クエリは答えるのが難しい。よってこういうのは逆から見るのが定石。つまり、クエリをすべて終えて削除し尽くした状態から開始して、辺をつないでいくのだ。

しかし一方では type 1 のクエリは、更新を含むクエリなので、その順に答えていかないと混乱してしまう。

こういうときは、Union-Find の連結状態を保存できる機能が欲しい。一つの方法として、「Union-Find のマージ過程を表す木」を構築する方法がある (詳細は略)。今回もバッチリ。

Union-Find のマージ過程を表す木では、頂点 と頂点 がマージされた瞬間に形成されたグループに対応する超頂点を用意していく。そしてその木を Euler Tour することで、そのときそのときのグループが「区間」として取り出せるのだ。

よって、今回の type 1 の操作も

• ある区間の最大値を求める
• その最大値を 0 で更新する

という操作だとみなせるので、セグ木で扱える。計算量は 。

#include <bits/stdc++.h>
using namespace std;

// Union-Find
struct UnionFind {
    vector<int> par;

    UnionFind() { }
    UnionFind(int n) : par(n, -1) { }
    void init(int n) { par.assign(n, -1); }
    
    int root(int x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }
    
    bool issame(int x, int y) {
        return root(x) == root(y);
    }
    
    bool merge(int x, int y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }
    
    int size(int x) {
        return -par[root(x)];
    }
};

// RMQ
template<class Monoid> struct RMQ {
    Monoid INF;
    int SIZE_R;
    vector<pair<Monoid,int> > dat;
    
    RMQ() {}
    RMQ(int n, const Monoid &inf): INF(inf) { 
        init(n, inf);
    }
    void init(int n, const Monoid &inf) {
        INF = inf;
        SIZE_R = 1;
        while (SIZE_R < n) SIZE_R *= 2;
        dat.assign(SIZE_R * 2, pair<Monoid,int>(INF, -1));
    }
    
    /* set, a is 0-indexed */
    void set(int a, const Monoid &v) { dat[a + SIZE_R] = make_pair(v, a); }
    void build() {
        for (int k = SIZE_R - 1; k > 0; --k) {
            dat[k] = max(dat[k*2], dat[k*2+1]);
        }
    }
    
    /* update, a is 0-indexed */
    void update(int a, const Monoid &v) {
        int k = a + SIZE_R;
        dat[k] = make_pair(v, a);
        while (k >>= 1) dat[k] = max(dat[k*2], dat[k*2+1]);
    }
    
    /* get {min-value, min-index}, a and b are 0-indexed */
    pair<Monoid,int> get(int a, int b) {
        pair<Monoid,int> vleft = make_pair(INF, -1), vright = make_pair(INF, -1);
        for (int left = a + SIZE_R, right = b + SIZE_R; left < right; left >>= 1, right >>= 1) {
            if (left & 1) vleft = max(vleft, dat[left++]);
            if (right & 1) vright = max(dat[--right], vright);
        }
        return max(vleft, vright);
    }
    inline Monoid operator [] (int a) { return dat[a + SIZE_R].first; }
    
    /* debug */
    void print() {
        for (int i = 0; i < SIZE_R; ++i) {
            Monoid val = (*this)[i];
            if (val != INF) cout << val;
            else cout << "INF";
            if (i != SIZE_R-1) cout << ",";
        }
        cout << endl;
    }
};

int main() {
    cin.tie(0); 
    ios::sync_with_stdio(false);

    int N, M, Q;
    cin >> N >> M >> Q;
    vector<int> C(N), X(M), Y(M);
    for (int i = 0; i < N; ++i) cin >> C[i];
    for (int i = 0; i < M; ++i) cin >> X[i] >> Y[i], --X[i], --Y[i];
    vector<int> type(Q), id(Q);
    set<int> delete_edge;
    for (int i = 0; i < Q; ++i) {
        cin >> type[i] >> id[i];
        --id[i];
        if (type[i] == 2) delete_edge.insert(id[i]);
    }
    
    // build tree
    UnionFind uf(N);
    vector<vector<int>> tree(N*2-1);
    vector<int> ancestor(N*2-1);
    iota(ancestor.begin(), ancestor.end(), 0);
    int V = N;
    auto merge = [&](int x, int y) -> void {
        x = uf.root(x), y = uf.root(y);
        if (x == y) return;
        uf.merge(x, y);
        if (uf.root(x) != x) swap(x, y);
        tree[V].push_back(ancestor[x]);
        tree[V].push_back(ancestor[y]);
        ancestor[x] = V++;
    };
    for (int i = 0; i < M; ++i) {
        if (delete_edge.count(i)) continue;
        merge(X[i], Y[i]);
    }

    // enroll queries
    vector<int> qnode(Q, -1);
    for (int i = Q-1; i >= 0; --i) {
        if (type[i] == 2) merge(X[id[i]], Y[id[i]]);
        else qnode[i] = ancestor[uf.root(id[i])];
    }
    
    // Euler Tour
    vector<int> left(N*2-1), right(N*2-1);
    int iter = 0;
    RMQ<int> rmq(N, -(1LL<<29));
    auto dfs = [&](auto self, int v) -> void {
        left[v] = iter;
        if (tree[v].empty()) rmq.set(iter++, C[v]);
        for (auto ch: tree[v]) self(self, ch);
        right[v] = iter;
    };
    for (int v = 0; v < N; ++v) {
        if (uf.root(v) != v) continue;
        dfs(dfs, ancestor[v]);
    }
    rmq.build();
        
    // query
    vector<int> res(Q, -1);
    for (int q = 0; q < Q; ++q) {
        if (type[q] == 2) continue;
        int v = qnode[q];
        auto tmp = rmq.get(left[v], right[v]);
        rmq.update(tmp.second, 0);
        res[q] = tmp.first;
    }
    for (auto val: res) if (val != -1) cout << val << endl;
}

別解：Undo 付き Union-Find

同じように操作を逆順に併合していって、改めてクエリの先頭からこなしていく方法も考えられそう。

type 2 の辺削除クエリは、undo 付き Union-Find の undo 機能によって実現できる (その辺削除がグループを分断するものであるかどうかはあらかじめ求めておく、分断するものでない場合は undo しない)。