Codeforces Round #395 (Div. 1): E. Timofey and our friends animals

,

http://codeforces.com/contest/763/problem/E

problem

単純グラフ$G$が与えられる。 次のようなクエリが$Q$個与えられるので処理せよ。

  • 頂点を番号$[l, r)$のものだけに制限してできる部分グラフ$H_{[l, r)} \subseteq G$の連結成分の数を答えよ。

ただし$G$の頂点$u, v$間に辺があるのは$|u - v| \le K \le 5$のときだけである。

solution

union-find木 + 平方分割 + 永続化。計算量は$O(N \alpha + M + Q \sqrt{N} K \alpha)$のような感じ。

愚直にやるにはunion-find木だが、クエリ毎に$M$回併合していると間に合わない。

ほとんど直線状のグラフである。$\sqrt{N}$個のchunksに平方分割できる。 union-find木を用意し、同じchunkに入る辺は先に張っておく。 経路圧縮も全てしておき、この状態$X$を保存しておく。 破壊的に処理した後この状態$X$を$O(\sqrt{N} K)$程度の計算量で復元できれば、クエリごとにunion-find木の残りの部分を単に処理して答えを出すだけである。

union-find木の永続化には複数可能性がある。 例えば永続配列によるもの。 今回は部分永続性だけでよいので単純なundoができればよい。 特に今回は同じ位置への操作回数が少ない(高々$O(\sqrt{N}K)$回)ので、内部の配列への書き込みの履歴を持っておいて復元の際はそれを書き戻していけば十分となる。 unordered_map等で上に一層被せるやつだと定数倍により間に合わない。

implementation

#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

struct disjoint_sets {
    vector<int> data;
    disjoint_sets() = default;
    explicit disjoint_sets(size_t n) : data(n, -1) {}
    bool is_root(int i) { return data[i] < 0; }
    int find_root(int i) { return is_root(i) ? i : (data[i] = find_root(data[i])); }
    int set_size(int i) { return - data[find_root(i)]; }
    int union_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            data[i] += data[j];
            data[j] = i;
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

struct wrapped_disjoint_sets {
    vector<int> a_data;
    stack<pair<int, int> > modified;
    explicit wrapped_disjoint_sets(disjoint_sets const & a_original) : a_data(a_original.data) {}
    int data(int i) {
        return a_data[i];
    }
    void data_set(int i, int j) {
        if (data(i) != j) {
            modified.emplace(i, a_data[i]);
            a_data[i] = j;
        }
    }
    void reset() {
        while (not modified.empty()) {
            int i, value; tie(i, value) = modified.top(); modified.pop();
            a_data[i] = value;
        }
    }
    bool is_root(int i) { return data(i) < 0; }
    int find_root(int i) { return is_root(i) ? i : find_root(data(i)); }
    int set_size(int i) { return - data(find_root(i)); }
    int union_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            data_set(i, data(i) + data(j));
            data_set(j, i);
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

int main() {
    int n, k, m; scanf("%d%d%d", &n, &k, &m);
    disjoint_sets splitted_ds(n);
    constexpr int bucket_width = 512; // fastest -- mod is unnecessary and appropriate size
    int bucket_count = ceil(n /(double) bucket_width);
    vector<vector<int> > edges(n);
    repeat (i,m) {
        int u, v; scanf("%d%d", &u, &v); -- u; -- v;
        if (u > v) swap(u, v);
        edges[u].push_back(v);
        int uj = u / bucket_width;
        int vj = v / bucket_width;
        if (uj == vj) {
            splitted_ds.union_sets(u, v);
        }
    }
    vector<int> cnts(bucket_count);
    repeat (i,n) {
        splitted_ds.find_root(i); // compress
        if (splitted_ds.is_root(i)) {
            int j = i / bucket_width;
            ++ cnts[j];
        }
    }
    wrapped_disjoint_sets wrapped_ds(splitted_ds);
    int q; scanf("%d", &q);
    while (q --) {
        int l, r; scanf("%d%d", &l, &r); -- l;
        int lj = l / bucket_width;
        int rj = r / bucket_width;
        wrapped_ds.reset();
        int cnt = 0;
        { // init
            int i = l;
            for (; i < r and i / bucket_width == lj; ++ i) {
                wrapped_ds.data_set(i, -1);
                ++ cnt;
            }
            for (; i / bucket_width < rj; i += bucket_width) {
                cnt += cnts[i / bucket_width];
            }
            for (; i < r; ++ i) {
                wrapped_ds.data_set(i, -1);
                ++ cnt;
            }
        }
        { // union
            int i = l;
            for (; i < r and i / bucket_width == lj; ++ i) {
                for (int j : edges[i]) if (j < r) {
                    if (not wrapped_ds.is_same(i, j)) {
                        wrapped_ds.union_sets(i, j);
                        -- cnt;
                    }
                }
            }
            for (; i / bucket_width < rj; i += bucket_width) {
                for (int di = bucket_width - k; di < bucket_width; ++ di) {
                    for (int j : edges[i+di]) if (j < r) {
                        if (not wrapped_ds.is_same(i+di, j)) {
                            wrapped_ds.union_sets(i+di, j);
                            -- cnt;
                        }
                    }
                }
            }
            for (; i < r; ++ i) {
                for (int j : edges[i]) if (j < r) {
                    if (not wrapped_ds.is_same(i, j)) {
                        wrapped_ds.union_sets(i, j);
                        -- cnt;
                    }
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}