library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub maspypy/library

:warning: setfunc/online/online_or_convolution.hpp

Depends on

Code

#include "setfunc/online/online_subset_zeta.hpp"
#include "setfunc/online/online_subset_mobius.hpp"

template <typename T>
struct Online_Or_Convolution {
  Online_Subset_Zeta<T> X1, X2;
  Online_Subset_Mobius<T> Y;
  Online_Or_Convolution(int LOG) : X1(LOG), X2(LOG), Y(LOG) {}
  // set a[i] and b[i], return conv(a,b)[i]
  T set(int i, T ai, T bi) { return Y.set(i, X1.set(i, ai) * X2.set(i, bi)); }
  // assume a[i],b[i], return zeta(a)[i]. not increment the pointer.
  T assume(int i, T ai, T bi) {
    return Y.assume(i, X1.assume(i, ai) * X2.assume(i, bi));
  }
};
#line 2 "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;
  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;
  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; }
#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 3 "setfunc/online/online_subset_zeta.hpp"

/*
segtree を考える
現在のポインタの位置がある
もう全部の値が読まれた subtree ではゼータされた状態にしておく
*/
template <typename T>
struct Online_Subset_Zeta {
  int n;
  int p = 0;
  vc<T> A;
  Online_Subset_Zeta(int LOG) : n(LOG), A(1 << n) {}

  // set a[i], return zeta(a)[i]
  T set(int i, T a) {
    assert(p == i);
    T ans = assume(i, 0) + a;
    A[p++] = a;
    int K = lowbit(p);
    for (int k = 0; k < K; ++k)
      for (int j = p - (1 << k); j < p; ++j) A[j] += A[j - (1 << k)];
    return ans;
  }

  // assume a[i], return zeta(a)[i]. not increment the pointer.
  T assume(int i, T ai) {
    assert(p == i);
    T ans = ai;
    enumerate_all_bit<u32>(i, [&](int j) -> void { ans += A[i - (1 << j)]; });
    return ans;
  }
};
#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 3 "setfunc/online/online_subset_mobius.hpp"

template <typename T>
struct Online_Subset_Mobius {
  int n;
  int p = 0;
  vc<T> A;
  Online_Subset_Mobius(int LOG) : n(LOG), A(1 << n) {}

  // set a[i], return zeta(a)[i]
  T set(int i, T a) {
    assert(p == i);
    T ans = assume(i, 0) + a;
    A[p++] = a;
    int K = lowbit(p);
    for (int k = 0; k < K; ++k)
      for (int j = p - (1 << k); j < p; ++j) A[j] -= A[j - (1 << k)];
    return ans;
  }

  // assume a[i], return zeta(a)[i]. not increment the pointer.
  T assume(int i, T ai) {
    assert(p == i);
    T ans = ai;
    enumerate_all_bit<u32>(i, [&](int j) -> vood { ans -= A[i - (1 << j)]; });
    return ans;
  }
};
#line 3 "setfunc/online/online_or_convolution.hpp"

template <typename T>
struct Online_Or_Convolution {
  Online_Subset_Zeta<T> X1, X2;
  Online_Subset_Mobius<T> Y;
  Online_Or_Convolution(int LOG) : X1(LOG), X2(LOG), Y(LOG) {}
  // set a[i] and b[i], return conv(a,b)[i]
  T set(int i, T ai, T bi) { return Y.set(i, X1.set(i, ai) * X2.set(i, bi)); }
  // assume a[i],b[i], return zeta(a)[i]. not increment the pointer.
  T assume(int i, T ai, T bi) {
    return Y.assume(i, X1.assume(i, ai) * X2.assume(i, bi));
  }
};
Back to top page