offline dynamic connectivity sum

ソースコード

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

仕様

Warning

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