dual segment tree

ソースコード

  1#include <iostream>
  2#include <vector>
  3#include <cassert>
  4using namespace std;
  5
  6// DualSegmentTree
  7namespace titan23 {
  8
  9  template <class T,
 10            class F,
 11            T (*mapping)(F, T),
 12            F (*composition)(F, F),
 13            T (*e)(),
 14            F (*id)()>
 15  struct DualSegmentTree {
 16
 17    int _n, _size, _log;
 18    vector<T> _data, _lazy;
 19
 20    DualSegmentTree() {}
 21
 22    DualSegmentTree(const int n) {
 23      _build(n);
 24    }
 25
 26    DualSegmentTree(const vector<T> &a) {
 27      int n = (int)a.size();
 28      _build(n);
 29      for (int i = 0; i < _n; ++i) {
 30        _data[i] = a[i];
 31      }
 32    }
 33
 34    void _build(const int n) {
 35      this->_n = n;
 36      this->_log = 32 - __builtin_clz(n);
 37      this->_size = 1 << _log;
 38      this->_data.resize(_n, e());
 39      this->_lazy.resize(_size, id());
 40    }
 41
 42    void _all_apply(int k, F f) {
 43      if (k < _size) {
 44        _lazy[k] = composition(f, _lazy[k]);
 45        return;
 46      }
 47      k -= _size;
 48      if (k < _n) {
 49        _data[k] = mapping(f, _data[k]);
 50      }
 51    }
 52
 53    void _propagate(const int k) {
 54      _all_apply(k<<1, _lazy[k]);
 55      _all_apply(k<<1|1, _lazy[k]);
 56      _lazy[k] = id();
 57    }
 58
 59    void apply_point(int k, F f) {
 60      k += _size;
 61      for (int i = _log; i > 0; --i) {
 62        _propagate(k >> i);
 63      }
 64      _data[k-_size] = mapping(f, _data[k-_size]);
 65    }
 66
 67    void apply(int l, int r, const F f) {
 68      if (l == r || f == id()) return;
 69      l += _size;
 70      r += _size;
 71      F _id = id();
 72      for (int i = _log; i > 0; --i) {
 73        if (((l >> i << i) != l) && (_lazy[l>>i] != _id)) {
 74          _propagate(l>>i);
 75        }
 76        if (((r >> i << i) != r) && (_lazy[(r-1)>>i] != _id)) {
 77          _propagate((r-1)>>i);
 78        }
 79      }
 80      if ((l-_size) & 1) {
 81        _data[l-_size] = mapping(f, _data[l-_size]);
 82        ++l;
 83      }
 84      if ((r-_size) & 1) {
 85        _data[(r-_size)^1] = mapping(f, _data[(r-_size)^1]);
 86        r ^= 1;
 87      }
 88      l >>= 1;
 89      r >>= 1;
 90      while (l < r) {
 91        if (l & 1) {
 92          _lazy[l] = composition(f, _lazy[l]);
 93          ++l;
 94        }
 95        if (r & 1) {
 96          --r;
 97          _lazy[r] = composition(f, _lazy[r]);
 98        }
 99        l >>= 1;
100        r >>= 1;
101      }
102    }
103
104    void all_apply(F f) {
105      _lazy[1] = composition(f, _lazy[1]);
106    }
107
108    void all_propagate() {
109      for (int i = 0;  i < _size; ++i) {
110        _propagate(i);
111      }
112    }
113
114    vector<T> tovector() const {
115      all_propagate();
116      vector<T> res = _data;
117      return res;
118    }
119
120    T get(int k) {
121      if (k < 0) k += _n;
122      k += _size;
123      for (int i = _log; i > 0; --i) {
124        _propagate(k>>i);
125      }
126      return _data[k-_size];
127    }
128
129    void set(int k, T v) {
130      if (k < 0) k += _n;
131      k += _size;
132      for (int i = _log; i > 0; --i) {
133        _propagate(k>>i);
134      }
135      _data[k-_size] = v;
136    }
137
138    void print() {
139      cout << '[';
140      for (int i = 0; i < _n-1; ++i) {
141        cout << get(i) << ", ";
142      }
143      cout << get(_n-1);
144      cout << ']' << endl;
145    }
146  };
147}  // namespace titan23

仕様

Warning

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