区間の集合を扱うデータ構造

range_set.cpp

#include <bits/stdc++.h>

struct Range {
  // [l, r)
  int l;
  int r;

  Range() : l(-1), r(-1) {}
  Range(int l, int r) : l(l), r(r) { fit(); }
  void fit() {
    if (r < l) r = l;
  }
  int len() const { return r - l; }
  std::pair<int, int> as_pair() const { return std::make_pair(l, r); }

#define DEF_BIN_OPS(op) \
  bool operator op(const Range &o) const { return as_pair() op o.as_pair(); }
  DEF_BIN_OPS(<)
  DEF_BIN_OPS(>)
  DEF_BIN_OPS(==)
  DEF_BIN_OPS(!=)
  DEF_BIN_OPS(<=)
  DEF_BIN_OPS(>=)
#undef DEF_BIN_OPS

  bool merge(const Range &o) {
    if (r < o.l || o.r < l) return false;
    l = std::min(l, o.l);
    r = std::max(r, o.r);
    fit();
    return true;
  }
  bool intersect(const Range &o) {
    if (r < o.l || o.r < l) return false;
    l = std::max(l, o.l);
    r = std::min(r, o.r);
    fit();
    return true;
  }

  std::string fmt() const {
    std::stringstream ss;
    ss << "[" << l << ", " << r << ")";
    return ss.str();
  }
};

struct RangeSet {
  std::map<int, Range> s;
  RangeSet() {}
  RangeSet(const std::vector<Range> &x) {
    for (auto &r : x) insert(r);
  }
  int length_sum() const {
    int ret = 0;
    for (const auto &r : s) {
      ret += r.second.len();
    }
    return ret;
  }
  bool contains(int p) const {
    auto itr = this->s.upper_bound(p);
    return (itr != this->s.end() && itr->second.l <= p);
  }
  void insert(const Range &range) {
    auto itr1 = this->s.lower_bound(range.l);
    auto itr2 = this->s.upper_bound(range.r);
    if (itr2 != this->s.end()) itr2++;
    Range tmp = range;
    for (auto itr = itr1; itr != itr2;) {
      bool merged = tmp.merge(itr->second);
      if (!merged) break;
      itr = this->s.erase(itr);
    }
    if (tmp.len()) this->s[tmp.r] = tmp;
  }
  void cut(const Range &range) {
    auto itr1 = this->s.upper_bound(range.l);
    auto itr2 = this->s.lower_bound(range.r);
    if (itr2 != this->s.end()) itr2++;
    Range r1, r2;
    for (auto itr = itr1; itr != itr2;) {
      Range tmp = itr->second;
      if (!tmp.intersect(range)) break;
      tmp = itr->second;
      Range split1(tmp.l, range.l);
      Range split2(range.r, tmp.r);
      if (split1.len()) r1 = split1;
      if (split2.len()) r2 = split2;
      itr = this->s.erase(itr);
    }
    if (r1.len()) this->insert(r1);
    if (r2.len()) this->insert(r2);
  }
  RangeSet operator&(const RangeSet &o) const {
    RangeSet ret;
    for (auto x : o.s) {
      const Range &range = x.second;
      auto itr1 = this->s.upper_bound(range.l);
      auto itr2 = this->s.lower_bound(range.r);
      if (itr2 != this->s.end()) itr2++;
      for (auto itr = itr1; itr != itr2; itr++) {
        Range tmp = itr->second;
        if (tmp.intersect(range)) {
          ret.s[tmp.r] = tmp;
        }
      }
    }
    return ret;
  }
  RangeSet operator+(const RangeSet &o) const {
    RangeSet ret = *this;
    for (auto x : o.s) {
      ret.insert(x.second);
    }
    return ret;
  }
  RangeSet operator-(const RangeSet &o) const {
    RangeSet ret = *this;
    for (auto x : o.s) {
      ret.cut(x.second);
    }
    return ret;
  }
  bool operator==(const RangeSet &o) const { return s == o.s; }
  bool operator!=(const RangeSet &o) const { return s != o.s; }

#define DEF_OPS(op) \
  RangeSet &operator op##=(const RangeSet &o) { return *this = (*this op o); }
  DEF_OPS(&)
  DEF_OPS(+)
  DEF_OPS(-)
#undef DEF_OPS

  std::string fmt() const {
    std::stringstream ss;
    ss << "{ ";
    for (auto x : s) {
      ss << x.second.fmt() << ", ";
    }
    ss << "}";
    return ss.str();
  }

  void check() {
    for (auto &x : s) {
      assert(x.second.len() > 0);
      assert(x.first == x.second.r);
    }
  }
};

struct RangeTest {
  void test_as_pair() {
    auto a = Range(0, 2);
    assert(a.as_pair() == std::make_pair(0, 2));
  }
  void test_op_1() {
    auto a = Range(0, 2);
    auto b = Range(1, 3);
    assert(a < b);
    assert(a <= b);
  }
  void test_op_2() {
    auto a = Range(0, 2);
    auto b = Range(0, 2);
    auto c = Range(0, 3);
    assert(a == b);
    assert(a != c);
  }
  void test_merge_1() {
    auto a = Range(0, 5);
    auto b = Range(5, 10);
    assert(a.merge(b));
    assert(a.l == 0);
    assert(a.r == 10);
  }
  void test_merge_2() {
    auto a = Range(0, 5);
    auto b = Range(3, 10);
    assert(a.merge(b));
    assert(a.l == 0);
    assert(a.r == 10);
  }
  void test_merge_3() {
    auto a = Range(3, 10);
    auto b = Range(0, 5);
    assert(a.merge(b));
    assert(a.l == 0);
    assert(a.r == 10);
  }
  void test_merge_4() {
    auto a = Range(5, 10);
    auto b = Range(0, 5);
    assert(a.merge(b));
    assert(a.l == 0);
    assert(a.r == 10);
  }
  void test_merge_5() {
    auto a = Range(0, 10);
    auto b = Range(3, 5);
    assert(a.merge(b));
    assert(a.l == 0);
    assert(a.r == 10);
  }
  void test_merge_6() {
    auto a = Range(3, 5);
    auto b = Range(0, 10);
    assert(a.merge(b));
    assert(a.l == 0);
    assert(a.r == 10);
  }
  void test_merge_7() {
    auto a = Range(3, 5);
    auto b = Range(6, 10);
    assert(!a.merge(b));
    assert(a.l == 3);
    assert(a.r == 5);
  }
  void test_intersect_1() {
    auto a = Range(0, 5);
    auto b = Range(5, 10);
    assert(a.intersect(b));
    assert(a.l == 5);
    assert(a.r == 5);
  }
  void test_intersect_2() {
    auto a = Range(0, 5);
    auto b = Range(3, 10);
    assert(a.intersect(b));
    assert(a.l == 3);
    assert(a.r == 5);
  }
  void test_intersect_3() {
    auto a = Range(3, 10);
    auto b = Range(0, 5);
    assert(a.intersect(b));
    assert(a.l == 3);
    assert(a.r == 5);
  }
  void test_intersect_4() {
    auto a = Range(5, 10);
    auto b = Range(0, 5);
    assert(a.intersect(b));
    assert(a.l == 5);
    assert(a.r == 5);
  }
  void test_intersect_5() {
    auto a = Range(0, 10);
    auto b = Range(3, 5);
    assert(a.intersect(b));
    assert(a.l == 3);
    assert(a.r == 5);
  }
  void test_intersect_6() {
    auto a = Range(3, 5);
    auto b = Range(0, 10);
    assert(a.intersect(b));
    assert(a.l == 3);
    assert(a.r == 5);
  }
  void test_intersect_7() {
    auto a = Range(3, 5);
    auto b = Range(6, 10);
    assert(!a.intersect(b));
  }
  RangeTest() {
    test_as_pair();
    test_op_1();
    test_op_2();
    test_merge_1();
    test_merge_2();
    test_merge_3();
    test_merge_4();
    test_merge_5();
    test_merge_6();
    test_merge_7();
    test_intersect_1();
    test_intersect_2();
    test_intersect_3();
    test_intersect_4();
    test_intersect_5();
    test_intersect_6();
    test_intersect_7();
  }
} test1;

struct RangeSetTest {
  void test_intersect_1() {
    auto a = RangeSet({Range(1, 3), Range(4, 5), Range(5, 10)});
    auto b = RangeSet({Range(2, 7)});
    auto actual = a & b;
    auto expected = RangeSet({Range(2, 3), Range(4, 5), Range(5, 7)});
    assert(actual == expected);
  }
  void test_intersect_2() {
    auto a = RangeSet({Range(2, 7)});
    auto b = RangeSet({Range(1, 3), Range(4, 5), Range(5, 10)});
    auto actual = a & b;
    auto expected = RangeSet({Range(2, 3), Range(4, 5), Range(5, 7)});
    assert(actual == expected);
  }
  void test_intersect_3() {
    auto a = RangeSet({Range(2, 7)});
    auto b = RangeSet({Range(10, 12)});
    auto actual = a & b;
    auto expected = RangeSet();
    assert(actual == expected);
  }
  void test_intersect_4() {
    auto a = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    auto b =
        RangeSet({Range(2, 7), Range(8, 10), Range(12, 15), Range(18, 30)});
    auto actual = a & b;
    auto expected = RangeSet({Range(2, 3), Range(4, 5), Range(5, 7),
                              Range(8, 10), Range(12, 15), Range(18, 20)});
    assert(actual == expected);
  }
  void test_intersect_5() {
    auto a = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    auto b = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    auto actual = a & b;
    auto expected = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    assert(actual == expected);
  }
  void test_intersect_6() {
    auto a = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    auto b = RangeSet();
    auto actual = a & b;
    auto expected = RangeSet();
    assert(actual == expected);
  }
  void test_insert_1() {
    auto a = RangeSet();
    a.insert(Range(1, 2));
    a.insert(Range(4, 5));
    auto expected = RangeSet({Range(1, 2), Range(4, 5)});
    assert(a == expected);
  }
  void test_insert_2() {
    auto a = RangeSet({Range(1, 2), Range(4, 5)});
    a.insert(Range(1, 2));
    a.insert(Range(1, 5));
    auto expected = RangeSet({Range(1, 5)});
    assert(a == expected);
  }
  void test_insert_3() {
    auto a = RangeSet({Range(1, 2), Range(4, 5)});
    a.insert(Range(5, 10));
    a.insert(Range(2, 4));
    auto expected = RangeSet({Range(1, 10)});
    assert(a == expected);
  }
  void test_insert_4() {
    auto a = RangeSet();
    for (int i = 1; i < 10; i++) {
      a.insert(Range(i, i + 1));
    }
    auto expected = RangeSet({Range(1, 10)});
    assert(a == expected);
  }
  void test_insert_5() {
    auto a = RangeSet({Range(1, 5), Range(10, 20)});
    a.insert(Range(3, 7));
    auto expected = RangeSet({Range(1, 7), Range(10, 20)});
    assert(a == expected);
  }
  void test_insert_6() {
    auto a = RangeSet({Range(1, 5), Range(10, 20)});
    a.insert(Range(7, 15));
    auto expected = RangeSet({Range(1, 5), Range(7, 20)});
    assert(a == expected);
  }
  void test_union_1() {
    auto a = RangeSet({Range(1, 3), Range(4, 5), Range(5, 10)});
    auto b = RangeSet({Range(2, 7)});
    auto actual = a + b;
    auto expected = RangeSet({Range(1, 10)});
    assert(actual == expected);
  }
  void test_union_2() {
    auto a = RangeSet({Range(2, 7)});
    auto b = RangeSet({Range(1, 3), Range(4, 5), Range(5, 10)});
    auto actual = a + b;
    auto expected = RangeSet({Range(1, 10)});
    assert(actual == expected);
  }
  void test_union_3() {
    auto a = RangeSet({Range(2, 7)});
    auto b = RangeSet({Range(10, 12)});
    auto actual = a + b;
    auto expected = RangeSet({Range(2, 7), Range(10, 12)});
    assert(actual == expected);
  }
  void test_union_4() {
    auto a = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    auto b =
        RangeSet({Range(2, 7), Range(8, 10), Range(12, 15), Range(18, 30)});
    auto actual = a + b;
    auto expected = RangeSet({Range(1, 30)});
    assert(actual == expected);
  }
  void test_union_5() {
    auto a = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    auto b = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    auto actual = a + b;
    auto expected = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    assert(actual == expected);
  }
  void test_union_6() {
    auto a = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    auto b = RangeSet();
    auto actual = a + b;
    auto expected = RangeSet({Range(1, 3), Range(4, 5), Range(5, 20)});
    assert(actual == expected);
  }
  void test_construct_1() {
    auto a = RangeSet(
        {Range(1, 5), Range(1, 5), Range(5, 7), Range(3, 4), Range(1, 10)});
    auto expected = RangeSet({Range(1, 10)});
    assert(a == expected);
  }
  void test_cut_1() {
    auto a = RangeSet({Range(1, 10)});
    a.cut(Range(3, 5));
    auto expected = RangeSet({Range(1, 3), Range(5, 10)});
    assert(a == expected);
  }
  void test_cut_2() {
    auto a = RangeSet({Range(1, 10)});
    a.cut(Range(5, 20));
    auto expected = RangeSet({Range(1, 5)});
    assert(a == expected);
  }
  void test_cut_3() {
    auto a = RangeSet({Range(10, 20)});
    a.cut(Range(5, 15));
    auto expected = RangeSet({Range(15, 20)});
    assert(a == expected);
  }
  void test_cut_4() {
    auto a = RangeSet({Range(1, 20)});
    a.cut(Range(1, 2));
    a.cut(Range(3, 4));
    a.cut(Range(5, 6));
    auto expected = RangeSet({Range(2, 3), Range(4, 5), Range(6, 20)});
    assert(a == expected);
  }
  void test_cut_5() {
    auto a = RangeSet({Range(10, 20)});
    a.cut(Range(1, 100));
    auto expected = RangeSet();
    assert(a == expected);
  }
  void test_cut_6() {
    auto a = RangeSet({Range(1, 5), Range(10, 20)});
    a.cut(Range(3, 7));
    auto expected = RangeSet({Range(1, 3), Range(10, 20)});
    assert(a == expected);
  }
  void test_cut_7() {
    auto a = RangeSet({Range(1, 5), Range(10, 20)});
    a.cut(Range(7, 12));
    auto expected = RangeSet({Range(1, 5), Range(12, 20)});
    assert(a == expected);
  }
  void test_exclude_1() {
    auto a = RangeSet({Range(1, 3), Range(5, 10)});
    auto b = RangeSet({Range(2, 7), Range(9, 15)});
    auto actual = a - b;
    auto expected = RangeSet({Range(1, 2), Range(7, 9)});
    assert(actual == expected);
  }
  void test_exclude_2() {
    auto a = RangeSet({Range(1, 3), Range(5, 10)});
    auto b = RangeSet();
    auto actual = a - b;
    auto expected = RangeSet({Range(1, 3), Range(5, 10)});
    assert(actual == expected);
  }
  void test_exclude_3() {
    auto a = RangeSet({Range(1, 3), Range(5, 10)});
    auto b = RangeSet({Range(100, 150)});
    auto actual = a - b;
    auto expected = RangeSet({Range(1, 3), Range(5, 10)});
    assert(actual == expected);
  }
  void test_contains_1() {
    auto a = RangeSet({Range(1, 3), Range(5, 10)});
    assert(a.contains(1));
    assert(a.contains(2));
    assert(!a.contains(3));
    assert(a.contains(5));
    assert(a.contains(6));
    assert(a.contains(9));
    assert(!a.contains(10));
  }
  RangeSetTest() {
    test_intersect_1();
    test_intersect_2();
    test_intersect_3();
    test_intersect_4();
    test_intersect_6();
    test_insert_1();
    test_insert_2();
    test_insert_3();
    test_insert_4();
    test_insert_5();
    test_insert_6();
    test_union_1();
    test_union_2();
    test_union_3();
    test_union_4();
    test_union_6();
    test_construct_1();
    test_cut_1();
    test_cut_2();
    test_cut_3();
    test_cut_4();
    test_cut_5();
    test_cut_6();
    test_cut_7();
    test_exclude_1();
    test_exclude_2();
    test_exclude_3();
    test_contains_1();
  }
} test2;

int main() {}

https://codeforces.com/contest/558/submission/84654015