setfunc/boolean_range_add_point_get.hpp

• View this file on GitHub
• Last update: 2026-08-19 06:34:57+09:00
• Include: #include "setfunc/boolean_range_add_point_get.hpp"

Depends on

• alg/monoid/add.hpp
• alg/monoid/xor.hpp
• enumerate/bits.hpp
• other/bit.hpp
• random/base.hpp
• random/shuffle.hpp

Code

#include "random/shuffle.hpp"
#include "alg/monoid/add.hpp"
#include "alg/monoid/xor.hpp"
#include "enumerate/bits.hpp"

// O((4/3)^LOG) per query
template <typename Monoid>
struct Boolean_Range_Add_Point_Get {
  using MX = Monoid;
  using X = typename MX::value_type;

  const int LOG;
  vc<X> S;
  array<u32, 3> mask;

  /*
  0: [x0,x1]
  1: [x0+x1,x0]
  2: [x0+x1,x1]
  */

  Boolean_Range_Add_Point_Get(int LOG) : LOG(LOG), mask{} {
    S.assign(1 << LOG, MX::unit());
    init_by_random();
  }

  void init_by_random() {
    mask[0] = mask[1] = mask[2] = 0;
    FOR(i, LOG) { mask[RNG(0, 3)] |= u32(1) << i; }
  }

  void init_by_query(const vc<pair<u32, u32>>& ADD, const vc<u32>& GET) {
    for (auto& [lo, hi] : ADD) assert((lo & ~hi) == 0);
    mask[0] = mask[1] = mask[2] = 0;

    auto eval = [&]() -> ll {
      ll ans = 0;

      for (auto& [lo, hi] : ADD) {
        u32 s = 0;
        s ^= (lo ^ hi) & mask[0];
        s ^= lo & mask[1];
        s ^= (~hi) & mask[2];
        ans += 1 << popcnt(s);
      }

      for (u32 i : GET) {
        u32 s = 0;
        s ^= (~i) & mask[1];
        s ^= i & mask[2];
        ans += 1 << popcnt(s);
      }

      return ans;
    };

    vc<int> I(LOG);
    FOR(i, LOG) I[i] = i;
    shuffle(I);

    array<ll, 3> c;
    for (int i : I) {
      FOR(k, 3) {
        mask[k] |= u32(1) << i, c[k] = eval(), mask[k] &= ~(u32(1) << i);
      }
      int k = min_element(all(c)) - c.begin();
      mask[k] |= u32(1) << i;
    }
  }

  void add(u32 lo, u32 hi, X x) {
    assert((lo & ~hi) == 0);

    u32 a = 0;
    u32 s = 0;
    u32 b = 0;

    a ^= lo & mask[0];
    s ^= (lo ^ hi) & mask[0];

    a ^= (~hi) & mask[1];
    s ^= lo & mask[1];
    b ^= lo & mask[1];

    a ^= lo & mask[2];
    s ^= (~hi) & mask[2];
    b ^= (~hi) & mask[2];

    enumerate_all_subset<u32, true>(s, [&](u32 t) -> void {
      X y = (__builtin_parity(t & b) ? MX::inverse(x) : x);
      S[a | t] = MX::op(S[a | t], y);
    });
  }

  X get(u32 i) {
    u32 a = i & mask[0];
    u32 s = 0;

    s ^= (~i) & mask[1];
    s ^= i & mask[2];

    X ANS = MX::unit();
    enumerate_all_subset<u32, true>(
        s, [&](u32 t) -> void { ANS = MX::op(ANS, S[a | t]); });
    return ANS;
  }
};

#line 1 "random/base.hpp"

u64 RNG_64() {
  static u64 x_ = u64(chrono::duration_cast<chrono::nanoseconds>(chrono::high_resolution_clock::now().time_since_epoch()).count()) * 10150724397891781847ULL;
  x_ ^= x_ << 7;
  return x_ ^= x_ >> 9;
}

u64 RNG(u64 lim) { return RNG_64() % lim; }

ll RNG(ll l, ll r) { return l + RNG_64() % (r - l); }
#line 2 "random/shuffle.hpp"

template <typename T>
void shuffle(vc<T>& A) {
  FOR(i, len(A)) {
    int j = RNG(0, i + 1);
    if (i != j) swap(A[i], A[j]);
  }
}
#line 1 "alg/monoid/add.hpp"

template <typename E>
struct Monoid_Add {
  using X = E;
  using value_type = X;
  static constexpr X op(const X &x, const X &y) noexcept { return x + y; }
  static constexpr X inverse(const X &x) noexcept { return -x; }
  static constexpr X power(const X &x, ll n) noexcept { return X(n) * x; }
  static constexpr X unit() { return X(0); }
  static constexpr bool commute = true;
};
#line 1 "alg/monoid/xor.hpp"

template <typename X>
struct Monoid_Xor {
  using value_type = X;
  static X op(X x, X y) { return x ^ y; }
  static constexpr X inverse(const X &x) noexcept { return x; }
  static constexpr X power(const X &x, ll n) noexcept {
    return (n & 1 ? x : 0);
  }
  static constexpr X unit(){return X(0);};
  static constexpr bool commute = true;
};
#line 1 "other/bit.hpp"

int popcnt(int x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(ll x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }
int popcnt_sgn(int x) { return (__builtin_parity(unsigned(x)) & 1 ? -1 : 1); }
int popcnt_sgn(u32 x) { return (__builtin_parity(x) & 1 ? -1 : 1); }
int popcnt_sgn(ll x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
int popcnt_sgn(u64 x) { return (__builtin_parityll(x) & 1 ? -1 : 1); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 1, 2)
int topbit(int x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(u32 x) { return (x == 0 ? -1 : 31 - __builtin_clz(x)); }
int topbit(ll x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
int topbit(u64 x) { return (x == 0 ? -1 : 63 - __builtin_clzll(x)); }
// (0, 1, 2, 3, 4) -> (-1, 0, 1, 0, 2)
int lowbit(int x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(u32 x) { return (x == 0 ? -1 : __builtin_ctz(x)); }
int lowbit(ll x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }
int lowbit(u64 x) { return (x == 0 ? -1 : __builtin_ctzll(x)); }

template <typename T>
T kth_bit(int k) {
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  UINT s;
  all_bit(UINT s) : s(s) {}
  struct iter {
    UINT s;
    int operator*() const { return lowbit(s); }
    void operator++() { s &= s - 1; }
    bool operator!=(nullptr_t) const { return s; }
  };
  iter begin() const { return {s}; }
  nullptr_t end() const { return nullptr; }
};

template <typename UINT>
struct all_subset {
  UINT s;
  all_subset(UINT s) : s(s) {}
  struct iter {
    UINT s, t;
    bool done = false;
    UINT operator*() const { return t; }
    void operator++() {
      done = (t == 0);
      t = (t - 1) & s;
    }
    bool operator!=(nullptr_t) const { return !done; }
  };
  iter begin() const { return {s, s}; }
  nullptr_t end() const { return nullptr; }
};

constexpr u64 full_mask(int n) { return n == 64 ? -1ULL : (1ULL << n) - 1; }

u64 bit_reverse(u64 x) {
  x = ((x & 0x5555555555555555ULL) << 1) | ((x >> 1) & 0x5555555555555555ULL);
  x = ((x & 0x3333333333333333ULL) << 2) | ((x >> 2) & 0x3333333333333333ULL);
  x = ((x & 0x0f0f0f0f0f0f0f0fULL) << 4) | ((x >> 4) & 0x0f0f0f0f0f0f0f0fULL);
  x = ((x & 0x00ff00ff00ff00ffULL) << 8) | ((x >> 8) & 0x00ff00ff00ff00ffULL);
  x = ((x & 0x0000ffff0000ffffULL) << 16) | ((x >> 16) & 0x0000ffff0000ffffULL);
  x = (x << 32) | (x >> 32);
  return x;
}
#line 2 "enumerate/bits.hpp"
template <typename BS, typename F>
void enumerate_bits_bitset(BS& b, int L, int R, F&& f) {
  if (L >= len(b)) return;
  int p = (b[L] ? L : b._Find_next(L));
  while (p < R) {
    f(p);
    p = b._Find_next(p);
  }
}

template <typename UINT, typename F>
inline void enumerate_all_bit(UINT s, F&& f) {
  static_assert(is_unsigned<UINT>::value);
  while (s) {
    f(lowbit(s));
    s &= s - 1;
  }
}

template <typename UINT, bool inc_empty, typename F>
inline void enumerate_all_subset(UINT s, F&& f) {
  static_assert(is_unsigned<UINT>::value);
  for (UINT t = s; t; t = (t - 1) & s) f(t);
  if constexpr (inc_empty) f(0);
}
#line 5 "setfunc/boolean_range_add_point_get.hpp"

// O((4/3)^LOG) per query
template <typename Monoid>
struct Boolean_Range_Add_Point_Get {
  using MX = Monoid;
  using X = typename MX::value_type;

  const int LOG;
  vc<X> S;
  array<u32, 3> mask;

  /*
  0: [x0,x1]
  1: [x0+x1,x0]
  2: [x0+x1,x1]
  */

  Boolean_Range_Add_Point_Get(int LOG) : LOG(LOG), mask{} {
    S.assign(1 << LOG, MX::unit());
    init_by_random();
  }

  void init_by_random() {
    mask[0] = mask[1] = mask[2] = 0;
    FOR(i, LOG) { mask[RNG(0, 3)] |= u32(1) << i; }
  }

  void init_by_query(const vc<pair<u32, u32>>& ADD, const vc<u32>& GET) {
    for (auto& [lo, hi] : ADD) assert((lo & ~hi) == 0);
    mask[0] = mask[1] = mask[2] = 0;

    auto eval = [&]() -> ll {
      ll ans = 0;

      for (auto& [lo, hi] : ADD) {
        u32 s = 0;
        s ^= (lo ^ hi) & mask[0];
        s ^= lo & mask[1];
        s ^= (~hi) & mask[2];
        ans += 1 << popcnt(s);
      }

      for (u32 i : GET) {
        u32 s = 0;
        s ^= (~i) & mask[1];
        s ^= i & mask[2];
        ans += 1 << popcnt(s);
      }

      return ans;
    };

    vc<int> I(LOG);
    FOR(i, LOG) I[i] = i;
    shuffle(I);

    array<ll, 3> c;
    for (int i : I) {
      FOR(k, 3) {
        mask[k] |= u32(1) << i, c[k] = eval(), mask[k] &= ~(u32(1) << i);
      }
      int k = min_element(all(c)) - c.begin();
      mask[k] |= u32(1) << i;
    }
  }

  void add(u32 lo, u32 hi, X x) {
    assert((lo & ~hi) == 0);

    u32 a = 0;
    u32 s = 0;
    u32 b = 0;

    a ^= lo & mask[0];
    s ^= (lo ^ hi) & mask[0];

    a ^= (~hi) & mask[1];
    s ^= lo & mask[1];
    b ^= lo & mask[1];

    a ^= lo & mask[2];
    s ^= (~hi) & mask[2];
    b ^= (~hi) & mask[2];

    enumerate_all_subset<u32, true>(s, [&](u32 t) -> void {
      X y = (__builtin_parity(t & b) ? MX::inverse(x) : x);
      S[a | t] = MX::op(S[a | t], y);
    });
  }

  X get(u32 i) {
    u32 a = i & mask[0];
    u32 s = 0;

    s ^= (~i) & mask[1];
    s ^= i & mask[2];

    X ANS = MX::unit();
    enumerate_all_subset<u32, true>(
        s, [&](u32 t) -> void { ANS = MX::op(ANS, S[a | t]); });
    return ANS;
  }
};

Back to top page