ds/intervals.hpp

• View this file on GitHub
• Last update: 2024-12-13 13:55:16+09:00
• Include: #include "ds/intervals.hpp"
• Link: View error logs on GitHub Actions
• Link: https://codeforces.com/contest/1638/problem/E

Depends on

• ds/fastset.hpp

Verified with

• test/5_atcoder/abc256d.test.cpp
• test/5_atcoder/abc256ex.test.cpp
• test/5_atcoder/abc256ex2.test.cpp

Code

#include "ds/fastset.hpp"

// FastSet で高速化したもの
template <typename T>
struct Intervals_Fast {
  const int LLIM, RLIM;
  const T none_val;
  // none_val でない区間の個数と長さ合計
  int total_num;
  int total_len;
  vc<T> dat;
  FastSet ss;

  Intervals_Fast(int N, T none_val) : LLIM(0), RLIM(N), none_val(none_val), total_num(0), total_len(0), dat(N, none_val), ss(N) { ss.insert(0); }

  // x を含む区間の情報の取得 l, r, t
  tuple<int, int, T> get(int x, bool ERASE = false) {
    int l = ss.prev(x);
    int r = ss.next(x + 1);
    T t = dat[l];
    if (t != none_val && ERASE) {
      --total_num, total_len -= r - l;
      dat[l] = none_val;
      merge_at(l);
      merge_at(r);
    }
    return {l, r, t};
  }

  // [L, R) 内の全データの取得
  // f(l,r,x)
  template <typename F>
  void enumerate_range(int L, int R, F f, bool ERASE = false) {
    assert(LLIM <= L && L <= R && R <= RLIM);
    if (L == R) return;
    if (!ERASE) {
      int l = ss.prev(L);
      while (l < R) {
        int r = ss.next(l + 1);
        f(max(l, L), min(r, R), dat[l]);
        l = r;
      }
      return;
    }
    // 半端なところの分割
    int p = ss.prev(L);
    if (p < L) {
      ss.insert(L);
      dat[L] = dat[p];
      if (dat[L] != none_val) ++total_num;
    }
    p = ss.next(R);
    if (R < p) {
      dat[R] = dat[ss.prev(R)];
      ss.insert(R);
      if (dat[R] != none_val) ++total_num;
    }
    p = L;
    while (p < R) {
      int q = ss.next(p + 1);
      T x = dat[p];
      f(p, q, x);
      if (dat[p] != none_val) --total_num, total_len -= q - p;
      ss.erase(p);
      p = q;
    }
    ss.insert(L);
    dat[L] = none_val;
  }

  void set(int L, int R, T t) {
    if (L == R) return;
    enumerate_range(
        L, R, [](int l, int r, T x) -> void {}, true);
    ss.insert(L);
    dat[L] = t;
    if (t != none_val) total_num++, total_len += R - L;
    merge_at(L);
    merge_at(R);
  }

  template <typename F>
  void enumerate_all(F f) {
    enumerate_range(0, RLIM, f, false);
  }

  void merge_at(int p) {
    if (p <= 0 || RLIM <= p) return;
    int q = ss.prev(p - 1);
    if (dat[p] == dat[q]) {
      if (dat[p] != none_val) --total_num;
      ss.erase(p);
    }
  }
};

// https://codeforces.com/contest/1638/problem/E
// 持つ値のタイプ T、座標タイプ X
// コンストラクタでは T none_val を指定する
// 先読み可能なら座圧して fastset の方が速い
template <typename T, typename X = ll>
struct Intervals {
  static constexpr X LLIM = -infty<X>;
  static constexpr X RLIM = infty<X>;
  T none_val;
  // const T none_val;
  // none_val でない区間の個数と長さ合計
  int total_num;
  X total_len;
  map<X, T> dat;

  Intervals(T none_val) : none_val(none_val), total_num(0), total_len(0) {
    dat[LLIM] = none_val;
    dat[RLIM] = none_val;
  }

  // x を含む区間の情報の取得 l, r, t
  tuple<X, X, T> get(X x, bool ERASE = false) {
    auto it2 = dat.upper_bound(x);
    auto it1 = prev(it2);
    auto [l, tl] = *it1;
    auto [r, tr] = *it2;
    if (tl != none_val && ERASE) {
      --total_num, total_len -= r - l;
      dat[l] = none_val;
      merge_at(l);
      merge_at(r);
    }
    return {l, r, tl};
  }

  // [L, R) 内の全データの取得 f(l, r, t)
  template <typename F>
  void enumerate_range(X L, X R, F f, bool ERASE = false) {
    assert(LLIM <= L && L <= R && R <= RLIM);
    if (!ERASE) {
      auto it = prev(dat.upper_bound(L));
      while ((*it).fi < R) {
        auto it2 = next(it);
        f(max((*it).fi, L), min((*it2).fi, R), (*it).se);
        it = it2;
      }
      return;
    }
    // 半端なところの分割
    auto p = prev(dat.upper_bound(L));
    if ((*p).fi < L) {
      dat[L] = (*p).se;
      if (dat[L] != none_val) ++total_num;
    }
    p = dat.lower_bound(R);
    if (R < (*p).fi) {
      T t = (*prev(p)).se;
      dat[R] = t;
      if (t != none_val) ++total_num;
    }
    p = dat.lower_bound(L);
    while (1) {
      if ((*p).fi >= R) break;
      auto q = next(p);
      T t = (*p).se;
      f((*p).fi, (*q).fi, t);
      if (t != none_val) --total_num, total_len -= (*q).fi - (*p).fi;
      p = dat.erase(p);
    }
    dat[L] = none_val;
  }

  void set(X L, X R, T t) {
    assert(L <= R);
    if (L == R) return;
    enumerate_range(
        L, R, [](int l, int r, T x) -> void {}, true);
    dat[L] = t;
    if (t != none_val) total_num++, total_len += R - L;
    merge_at(L);
    merge_at(R);
  }

  template <typename F>
  void enumerate_all(F f) {
    enumerate_range(LLIM, RLIM, f, false);
  }

  void merge_at(X p) {
    if (p == LLIM || RLIM == p) return;
    auto itp = dat.lower_bound(p);
    assert((*itp).fi == p);
    auto itq = prev(itp);
    if ((*itp).se == (*itq).se) {
      if ((*itp).se != none_val) --total_num;
      dat.erase(itp);
    }
  }
};

#line 2 "ds/fastset.hpp"

// 64-ary tree

// space: (N/63) * u64

struct FastSet {
  static constexpr u32 B = 64;
  int n, log;
  vvc<u64> seg;

  FastSet() {}
  FastSet(int n) { build(n); }

  int size() { return n; }

  template <typename F>
  FastSet(int n, F f) {
    build(n, f);
  }

  void build(int m) {
    seg.clear();
    n = m;
    do {
      seg.push_back(vc<u64>((m + B - 1) / B));
      m = (m + B - 1) / B;
    } while (m > 1);
    log = len(seg);
  }
  template <typename F>
  void build(int n, F f) {
    build(n);
    FOR(i, n) { seg[0][i / B] |= u64(f(i)) << (i % B); }
    FOR(h, log - 1) {
      FOR(i, len(seg[h])) { seg[h + 1][i / B] |= u64(bool(seg[h][i])) << (i % B); }
    }
  }

  bool operator[](int i) const { return seg[0][i / B] >> (i % B) & 1; }
  void insert(int i) {
    assert(0 <= i && i < n);
    for (int h = 0; h < log; h++) { seg[h][i / B] |= u64(1) << (i % B), i /= B; }
  }
  void add(int i) { insert(i); }
  void erase(int i) {
    assert(0 <= i && i < n);
    u64 x = 0;
    for (int h = 0; h < log; h++) {
      seg[h][i / B] &= ~(u64(1) << (i % B));
      seg[h][i / B] |= x << (i % B);
      x = bool(seg[h][i / B]);
      i /= B;
    }
  }
  void remove(int i) { erase(i); }

  // min[x,n) or n

  int next(int i) {
    assert(i <= n);
    chmax(i, 0);
    for (int h = 0; h < log; h++) {
      if (i / B == seg[h].size()) break;
      u64 d = seg[h][i / B] >> (i % B);
      if (!d) {
        i = i / B + 1;
        continue;
      }
      i += lowbit(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += lowbit(seg[g][i / B]);
      }
      return i;
    }
    return n;
  }

  // max [0,x], or -1

  int prev(int i) {
    assert(i >= -1);
    if (i >= n) i = n - 1;
    for (int h = 0; h < log; h++) {
      if (i == -1) break;
      u64 d = seg[h][i / B] << (63 - i % B);
      if (!d) {
        i = i / B - 1;
        continue;
      }
      i -= __builtin_clzll(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += topbit(seg[g][i / B]);
      }
      return i;
    }
    return -1;
  }

  bool any(int l, int r) { return next(l) < r; }

  // [l, r)

  template <typename F>
  void enumerate(int l, int r, F f) {
    for (int x = next(l); x < r; x = next(x + 1)) f(x);
  }

  string to_string() {
    string s(n, '?');
    for (int i = 0; i < n; ++i) s[i] = ((*this)[i] ? '1' : '0');
    return s;
  }
};
#line 2 "ds/intervals.hpp"

// FastSet で高速化したもの
template <typename T>
struct Intervals_Fast {
  const int LLIM, RLIM;
  const T none_val;
  // none_val でない区間の個数と長さ合計
  int total_num;
  int total_len;
  vc<T> dat;
  FastSet ss;

  Intervals_Fast(int N, T none_val) : LLIM(0), RLIM(N), none_val(none_val), total_num(0), total_len(0), dat(N, none_val), ss(N) { ss.insert(0); }

  // x を含む区間の情報の取得 l, r, t
  tuple<int, int, T> get(int x, bool ERASE = false) {
    int l = ss.prev(x);
    int r = ss.next(x + 1);
    T t = dat[l];
    if (t != none_val && ERASE) {
      --total_num, total_len -= r - l;
      dat[l] = none_val;
      merge_at(l);
      merge_at(r);
    }
    return {l, r, t};
  }

  // [L, R) 内の全データの取得
  // f(l,r,x)
  template <typename F>
  void enumerate_range(int L, int R, F f, bool ERASE = false) {
    assert(LLIM <= L && L <= R && R <= RLIM);
    if (L == R) return;
    if (!ERASE) {
      int l = ss.prev(L);
      while (l < R) {
        int r = ss.next(l + 1);
        f(max(l, L), min(r, R), dat[l]);
        l = r;
      }
      return;
    }
    // 半端なところの分割
    int p = ss.prev(L);
    if (p < L) {
      ss.insert(L);
      dat[L] = dat[p];
      if (dat[L] != none_val) ++total_num;
    }
    p = ss.next(R);
    if (R < p) {
      dat[R] = dat[ss.prev(R)];
      ss.insert(R);
      if (dat[R] != none_val) ++total_num;
    }
    p = L;
    while (p < R) {
      int q = ss.next(p + 1);
      T x = dat[p];
      f(p, q, x);
      if (dat[p] != none_val) --total_num, total_len -= q - p;
      ss.erase(p);
      p = q;
    }
    ss.insert(L);
    dat[L] = none_val;
  }

  void set(int L, int R, T t) {
    if (L == R) return;
    enumerate_range(
        L, R, [](int l, int r, T x) -> void {}, true);
    ss.insert(L);
    dat[L] = t;
    if (t != none_val) total_num++, total_len += R - L;
    merge_at(L);
    merge_at(R);
  }

  template <typename F>
  void enumerate_all(F f) {
    enumerate_range(0, RLIM, f, false);
  }

  void merge_at(int p) {
    if (p <= 0 || RLIM <= p) return;
    int q = ss.prev(p - 1);
    if (dat[p] == dat[q]) {
      if (dat[p] != none_val) --total_num;
      ss.erase(p);
    }
  }
};

// https://codeforces.com/contest/1638/problem/E
// 持つ値のタイプ T、座標タイプ X
// コンストラクタでは T none_val を指定する
// 先読み可能なら座圧して fastset の方が速い
template <typename T, typename X = ll>
struct Intervals {
  static constexpr X LLIM = -infty<X>;
  static constexpr X RLIM = infty<X>;
  T none_val;
  // const T none_val;
  // none_val でない区間の個数と長さ合計
  int total_num;
  X total_len;
  map<X, T> dat;

  Intervals(T none_val) : none_val(none_val), total_num(0), total_len(0) {
    dat[LLIM] = none_val;
    dat[RLIM] = none_val;
  }

  // x を含む区間の情報の取得 l, r, t
  tuple<X, X, T> get(X x, bool ERASE = false) {
    auto it2 = dat.upper_bound(x);
    auto it1 = prev(it2);
    auto [l, tl] = *it1;
    auto [r, tr] = *it2;
    if (tl != none_val && ERASE) {
      --total_num, total_len -= r - l;
      dat[l] = none_val;
      merge_at(l);
      merge_at(r);
    }
    return {l, r, tl};
  }

  // [L, R) 内の全データの取得 f(l, r, t)
  template <typename F>
  void enumerate_range(X L, X R, F f, bool ERASE = false) {
    assert(LLIM <= L && L <= R && R <= RLIM);
    if (!ERASE) {
      auto it = prev(dat.upper_bound(L));
      while ((*it).fi < R) {
        auto it2 = next(it);
        f(max((*it).fi, L), min((*it2).fi, R), (*it).se);
        it = it2;
      }
      return;
    }
    // 半端なところの分割
    auto p = prev(dat.upper_bound(L));
    if ((*p).fi < L) {
      dat[L] = (*p).se;
      if (dat[L] != none_val) ++total_num;
    }
    p = dat.lower_bound(R);
    if (R < (*p).fi) {
      T t = (*prev(p)).se;
      dat[R] = t;
      if (t != none_val) ++total_num;
    }
    p = dat.lower_bound(L);
    while (1) {
      if ((*p).fi >= R) break;
      auto q = next(p);
      T t = (*p).se;
      f((*p).fi, (*q).fi, t);
      if (t != none_val) --total_num, total_len -= (*q).fi - (*p).fi;
      p = dat.erase(p);
    }
    dat[L] = none_val;
  }

  void set(X L, X R, T t) {
    assert(L <= R);
    if (L == R) return;
    enumerate_range(
        L, R, [](int l, int r, T x) -> void {}, true);
    dat[L] = t;
    if (t != none_val) total_num++, total_len += R - L;
    merge_at(L);
    merge_at(R);
  }

  template <typename F>
  void enumerate_all(F f) {
    enumerate_range(LLIM, RLIM, f, false);
  }

  void merge_at(X p) {
    if (p == LLIM || RLIM == p) return;
    auto itp = dat.lower_bound(p);
    assert((*itp).fi == p);
    auto itq = prev(itp);
    if ((*itp).se == (*itq).se) {
      if ((*itp).se != none_val) --total_num;
      dat.erase(itp);
    }
  }
};

Back to top page