alg/monoid/bitwise_function.hpp

View this file on GitHub
Last update: 2023-11-08 21:49:23+09:00
Include: #include "alg/monoid/bitwise_function.hpp"

Verified with

test/yukicoder/2498.test.cpp

Code

#pragma once

// composition of bitwise operation
// 0 -> a, -1 -> b
template <typename UINT>
struct Bitwise_Function {
  static_assert(is_same_v<UINT, u32> || is_same_v<UINT, u64>);
  using value_type = pair<UINT, UINT>;
  using X = value_type;
  static X op(X x, X y) { return {eval(y, x.fi), eval(y, x.se)}; }
  static UINT eval(X f, UINT x) { return (f.fi & (~x)) | (f.se & x); }
  static X func_or(UINT x) { return {x, UINT(-1)}; }
  static X func_and(UINT x) { return {0, x}; }
  static X func_xor(UINT x) { return {x, UINT(-1) ^ x}; }
  static constexpr X unit() { return {UINT(0), UINT(-1)}; }
  static constexpr bool commute = 0;
};

#line 2 "alg/monoid/bitwise_function.hpp"

// composition of bitwise operation
// 0 -> a, -1 -> b
template <typename UINT>
struct Bitwise_Function {
  static_assert(is_same_v<UINT, u32> || is_same_v<UINT, u64>);
  using value_type = pair<UINT, UINT>;
  using X = value_type;
  static X op(X x, X y) { return {eval(y, x.fi), eval(y, x.se)}; }
  static UINT eval(X f, UINT x) { return (f.fi & (~x)) | (f.se & x); }
  static X func_or(UINT x) { return {x, UINT(-1)}; }
  static X func_and(UINT x) { return {0, x}; }
  static X func_xor(UINT x) { return {x, UINT(-1) ^ x}; }
  static constexpr X unit() { return {UINT(0), UINT(-1)}; }
  static constexpr bool commute = 0;
};