segment_cover.h


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <concepts>
#include <functional>
#include <limits>
#include <map>

template <typename T, std::integral K = int> class SegmentCover {
  void cut(K k) {
    auto it = std::prev(segs.upper_bound(k));
    if (it->first < k) {
      segs[k] = it->second;
    }
  }

public:
  explicit SegmentCover(T v) {
    segs[std::numeric_limits<K>::min()] = segs[std::numeric_limits<K>::max()] =
        v;
  }

  // set [l, r) to v
  void cover(K l, K r, T v, const std::function<void(K, K, T)> &cb) {
    cut(l);
    cut(r);
    auto it = segs.find(l);
    while (it->first < r) {
      auto iit = std::next(it);
      cb(it->first, iit->first, it->second);
      segs.erase(it);
      it = iit;
    }
    segs[l] = v;
  }

  std::map<K, T> segs;
};