dual commutative segment tree

ソースコード

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

仕様

Warning

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