「競プロ!!」 競技プログラミング Advent Calendar 2017 の 14 日目の記事です。
補足 実装例
スライドに載せたコードの実装例を載せてあります。
モノイドをのせるセグメント木(RMQ) [p13,p15]
struct SegNode { int v; SegNode(int v) : v(v) {} SegNode operator*(const SegNode &r) const { return (v < r.v ? *this : r); } } e(1 << 30); struct SegmentTree { int sz; vector< SegNode > seg; SegmentTree(int n) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz - 1, e); } void update(int k, const SegNode &x) { k += sz - 1; seg[k] = x; while(k > 0) { k = (k - 1) >> 1; seg[k] = seg[2 * k + 1] * seg[2 * k + 2]; } } SegNode query(int a, int b, int k, int l, int r) { if(r <= a || b <= l) return (e); if(a <= l && r <= b) return (seg[k]); return (query(a, b, 2 * k + 1, l, (l + r) >> 1) * query(a, b, 2 * k + 2, (l + r) >> 1, r)); } SegNode query(int a, int b) { return (query(a, b, 0, 0, sz)); } };
区間内かつ x 以下の値を持つ要素のうち最右の位置を見つける二分探索 [p22]
struct SegNode { int v; SegNode(int v) : v(v) {} SegNode operator*(const SegNode &r) const { return (v < r.v ? *this : r); } } e(1 << 30); struct SegmentTree { int sz; vector< SegNode > seg; SegmentTree(int n) { sz = 1; while(sz < n) sz <<= 1; seg.assign(2 * sz - 1, e); } void update(int k, const SegNode &x) { k += sz - 1; seg[k] = x; while(k > 0) { k = (k - 1) >> 1; seg[k] = seg[2 * k + 1] * seg[2 * k + 2]; } } SegNode query(int a, int b, int k, int l, int r) { if(a >= r || b <= l) return (e); if(a <= l && r <= b) return (seg[k]); return (query(a, b, 2 * k + 1, l, (l + r) >> 1) * query(a, b, 2 * k + 2, (l + r) >> 1, r)); } SegNode query(int a, int b) { return (query(a, b, 0, 0, sz)); } int find(int a, int b, int x, int k, int l, int r) { if(seg[k].v > x || r <= a || b <= l) return (-1); if(k >= sz - 1) return (k - (sz - 1)); int rv = find(a, b, x, 2 * k + 2, (l + r) >> 1, r); if(rv != -1) return (rv); return (find(a, b, x, 2 * k + 1, l, (l + r) >> 1)); } int find(int a, int b, int x) { return (find(a, b, x, 0, 0, sz)); } };
Dynamic-connectivity [p74]
using edge = pair< int, int >; struct UnionFind { vector< int > data; stack< pair< int, int > > st; UnionFind(int sz) { data.assign(sz, -1); } bool unite(int x, int y) { x = find(x), y = find(y); st.emplace(x, data[x]); st.emplace(y, data[y]); if(x == y) return (false); if(data[x] > data[y]) swap(x, y); data[x] += data[y]; data[y] = x; return (true); } int find(int k) { if(data[k] < 0) return (k); return (find(data[k])); } int size(int k) { return (-data[find(k)]); } void undo() { data[st.top().first] = st.top().second; st.pop(); data[st.top().first] = st.top().second; st.pop(); } }; struct Dynamic_connectivity { UnionFind uf; int n, sz; vector< vector< edge > > edges; vector< pair< pair< int, int >, edge > > pending; map< edge, int > cnt, appear; Dynamic_connectivity(int n, int q) : n(q), uf(n) // (2018-03-21修正) { sz = 1; while(sz < n) sz <<= 1; edges.resize(2 * sz - 1); } void insert(int idx, edge e) { if(e.first > e.second) swap(e.first, e.second); if(cnt[e]++ == 0) appear[e] = idx; } void erase(int idx, edge e) { if(e.first > e.second) swap(e.first, e.second); if(--cnt[e] == 0) pending.emplace_back(make_pair(appear[e], idx), e); } void add(int a, int b, const edge &e, int k, int l, int r) { if(r <= a || b <= l) return; if(a <= l && r <= b) { edges[k].emplace_back(e); return; } add(a, b, e, 2 * k + 1, l, (l + r) >> 1); add(a, b, e, 2 * k + 2, (l + r) >> 1, r); } void add(int a, int b, const edge &e) { add(a, b, e, 0, 0, sz); } void build() { for(auto &p : cnt) { if(p.second > 0) pending.emplace_back(make_pair(appear[p.first], sz), p.first); } for(auto &s : pending) { add(s.first.first, s.first.second, s.second); } } void execute(const function< void(int) > &f, int k = 0) { for(auto &e : edges[k]) { int a, b; tie(a, b) = e; uf.unite(a, b); } if(k < sz - 1) { execute(f, 2 * k + 1); execute(f, 2 * k + 2); } else if(k - (sz - 1) < n) { int query_index = k - (sz - 1); f(query_index); } for(auto &e : edges[k]) { uf.undo(); } } };
辺の追加削除でデータを変換するのがわりと虚無なので, insert(クエリ時刻, edge), erase(クエリ時刻, edge) を呼び出してすべての辺を追加削除した後に, build() を呼び出すことでいい感じにデータを変換してセグメント木に辺をはるようになっています。
(verified:
Dynamic connectivity contest A. Connect and Disconnect http://codeforces.com/gym/100551/submission/33216575)
Fractional-cascading [p99,p104,p105]
struct SegmentTreeFractionalCascading { vector< vector< int > > seg; vector< vector< int > > L, R; int sz; SegmentTreeFractionalCascading(vector< vector< int > > &array) { sz = 1; while(sz < array.size()) sz <<= 1; seg.resize(2 * sz - 1); L.resize(2 * sz - 1); R.resize(2 * sz - 1); for(int k = 0; k < array.size(); k++) { seg[k + sz - 1] = array[k]; sort(begin(seg[k + sz - 1]), end(seg[k + sz - 1])); } for(int k = sz - 2; k >= 0; k--) { seg[k].resize(seg[2 * k + 1].size() + seg[2 * k + 2].size()); L[k].resize(seg[k].size() + 1); R[k].resize(seg[k].size() + 1); merge(begin(seg[2 * k + 1]), end(seg[2 * k + 1]), begin(seg[2 * k + 2]), end(seg[2 * k + 2]), begin(seg[k])); int tail1 = 0, tail2 = 0; for(int i = 0; i < seg[k].size(); i++) { L[k][i] = tail1, R[k][i] = tail2; if(tail1 < seg[2 * k + 1].size() && seg[2 * k + 1][tail1] == seg[k][i]) { ++tail1; } else { ++tail2; } } L[k][seg[k].size()] = (int) seg[2 * k + 1].size(); R[k][seg[k].size()] = (int) seg[2 * k + 2].size(); } } int query(int a, int b, int lower, int upper, int k, int l, int r) { if(r <= a || b <= l) { return (0); } else if(a <= l && r <= b) { return (upper - lower); } else { return (query(a, b, L[k][lower], L[k][upper], 2 * k + 1, l, (l + r) >> 1) + query(a, b, R[k][lower], R[k][upper], 2 * k + 2, (l + r) >> 1, r)); } } int query(int a, int b, int l, int r) { l = lower_bound(begin(seg[0]), end(seg[0]), l) - begin(seg[0]); r = lower_bound(begin(seg[0]), end(seg[0]), r) - begin(seg[0]); return (query(a, b, l, r, 0, 0, sz)); } };