offline dynamic connectivity

ソースコード

  1#include <vector>
  2#include <cassert>
  3#include <unordered_map>
  4#include <ext/pb_ds/assoc_container.hpp>
  5
  6#include "titan_cpplib/data_structures/undoable_union_find.cpp"
  7using namespace std;
  8
  9// OfflineDynamicConnectivity
 10namespace titan23 {
 11
 12    class OfflineDynamicConnectivity {
 13      private:
 14        int _n, _query_count, _size, _q;
 15        long long _bit, _msk;
 16        unordered_map<long long, pair<int, int>> start;
 17        vector<vector<long long>> data;
 18        vector<tuple<int, int, long long>> edge_data;
 19
 20        int bit_length(const int n) const {
 21            if (n == 0) return 0;
 22            return 32 - __builtin_clz(n);
 23        }
 24
 25        void _internal_add(int l, int r, const long long edge) {
 26            l += _size;
 27            r += _size;
 28            while (l < r) {
 29                if (l & 1) data[l++].emplace_back(edge);
 30                if (r & 1) data[--r].emplace_back(edge);
 31                l >>= 1;
 32                r >>= 1;
 33            }
 34        }
 35
 36      public:
 37        titan23::UndoableUnionFind uf;
 38
 39        OfflineDynamicConnectivity(const int n, const int q) :
 40                _n(n),
 41                _query_count(0),
 42                _size(1 << (bit_length(q-1))),
 43                _q(q),
 44                _bit(bit_length(n) + 1),
 45                _msk((1ll << (bit_length(n) + 1)) - 1),
 46                data(_size<<1),
 47                uf(n) {
 48            start.reserve(_q);
 49            edge_data.reserve(_q);
 50        }
 51
 52        void add_edge(const int u, const int v) {
 53            auto [s, t] = minmax(u, v);
 54            long long edge = (long long)s<<_bit|t;
 55            if (start[edge].first == 0) {
 56                start[edge].second = _query_count;
 57            }
 58            ++start[edge].first;
 59        }
 60
 61        void delete_edge(const int u, const int v) {
 62            auto [s, t] = minmax(u, v);
 63            long long edge = (long long)s<<_bit|t;
 64            auto it = start.find(edge);
 65            if (it->second.first == 1) {
 66                edge_data.emplace_back(it->second.second, _query_count, edge);
 67            }
 68            --it->second.first;
 69        }
 70
 71        void next_query() {
 72            ++_query_count;
 73        }
 74
 75        template<typename F> // void out(int k) {}
 76        void run(F &&out) {
 77            assert(_query_count <= _q);
 78            for (const auto &[edge, p]: start) {
 79                if (p.first != 0) {
 80                    _internal_add(p.second, _query_count, edge);
 81                }
 82            }
 83            for (const auto &[l, r, edge]: edge_data) {
 84                _internal_add(l, r, edge);
 85            }
 86            int size2 = _size<<1;
 87            int ptr = 0;
 88            int todo[bit_length(_q)<<2];
 89            todo[++ptr] = 1;
 90            while (ptr) {
 91                int v = todo[ptr--];
 92                if (v >= 0) {
 93                    for (const long long &uv: data[v]) {
 94                        uf.unite(uv>>_bit, uv&_msk);
 95                    }
 96                    todo[++ptr] = ~v;
 97                    if ((v<<1|1) < size2) {
 98                        todo[++ptr] = v<<1|1;
 99                        todo[++ptr] = v<<1;
100                    } else if (v - _size < _query_count) {
101                        out(v-_size);
102                    }
103                } else {
104                    int s = data[~v].size();
105                    for (int i = 0; i < s; ++i) {
106                        uf.undo();
107                    }
108                }
109            }
110        }
111    };
112}  // namespace titan23

仕様

Warning

doxygenfile: Cannot find file “titan_cpplib/data_structures/offline_dynamic_connectivity.cpp