2020-12-26

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

Codeforces CodeforcesR2600 CodeforcesDIV1-D データ構造クエリ処理問題クエリ(グラフ上) クエリ(木上) Union-Find undoつきUnion-Find Union-Findのマージ過程を表す木を考える部分永続Union-Find クエリ:削除 Eulerツアーセグメント木色に関する問題グラフクエリ先読み後ろから解く操作を逆順に見る個人的要復習

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

問題へのリンク

問題概要

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

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

制約

$1 \le N \le 2 \times 10^{5}$
$1 \le M \le 3 \times 10^{5}$
$1 \le Q \le 5 \times 10^{5}$

考えたこと

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

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

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

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

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

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

という操作だとみなせるので、セグ木で扱える。計算量は $O(N + M \alpha(N) + Q \log N)$ 。

#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 しない)。

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

問題概要

制約

考えたこと

別解：Undo 付き Union-Find