ds/doubling.hpp

• View this file on GitHub
• Last update: 2026-08-30 21:09:36+09:00
• Include: #include "ds/doubling.hpp"

Depends on

• alg/monoid/add.hpp
• other/bit.hpp

Verified with

• test/3_yukicoder/1097.test.cpp
• test/3_yukicoder/1977.test.cpp
• test/3_yukicoder/2242.test.cpp

Code

#include "other/bit.hpp"

#include "alg/monoid/add.hpp"


// 状態 a から 1 回操作すると、状態 b に遷移し、モノイドの元 x を加える。

// 行き先がない場合：-1 （add 不要）

template <typename Monoid, int LOG>
struct Doubling {
  using X = typename Monoid::value_type;
  int N;
  bool is_prepared;
  vvc<int> TO;
  vvc<X> DP;

  Doubling(int N) : N(N), is_prepared(0) {
    TO.assign(LOG, vc<int>(N, -1));
    DP.assign(LOG, vc<X>(N, Monoid::id()));
  }

  void add(int i, int to, X x) {
    assert(!is_prepared);
    assert(-1 <= to && to < N);
    TO[0][i] = to;
    DP[0][i] = x;
  }

  void build() {
    assert(!is_prepared);
    is_prepared = 1;
    FOR(k, LOG - 1) {
      FOR(v, N) {
        int w = TO[k][v];
        if (w == -1) {
          TO[k + 1][v] = -1;
          DP[k + 1][v] = DP[k][v];
          continue;
        }
        TO[k + 1][v] = TO[k][w];
        DP[k + 1][v] = Monoid::op(DP[k][v], DP[k][w]);
      }
    }
  }

  // (to, val)

  pair<int, X> calc(int i, ll step) {
    assert(is_prepared);
    assert(0 <= step && step < (1LL << LOG));
    X x = Monoid::id();
    while (step && i != -1) {
      int k = topbit(step);
      step ^= 1LL << k;
      x = Monoid::op(x, DP[k][i]);
      i = TO[k][i];
    }
    return {i, x};
  }

  // check(to, monoid_sum)

  template <typename F>
  ll max_step(F check, int i) {
    assert(is_prepared);
    X x = Monoid::id();
    ll step = 0;
    assert(check(i, x));
    FOR_R(k, LOG) {
      int j = TO[k][i];
      if (j == -1) continue;
      X y = Monoid::op(x, DP[k][i]);
      if (check(j, y)) {
        step |= 1LL << k;
        i = j;
        x = y;
        assert(i != -1);
      }
    }
    return step;
  }

  void debug() {
    print("TO");
    FOR(k, LOG) print(TO[k]);
    print("DP");
    FOR(k, LOG) print(DP[k]);
  }
};

#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) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return T(1) << k;
}
template <typename T>
bool has_kth_bit(T x, int k) {
  assert(0 <= k && k < int(8 * sizeof(T)));
  return x >> k & 1;
}

template <typename UINT>
struct all_bit {
  static_assert(is_unsigned<UINT>::value);
  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 {
  static_assert(is_unsigned<UINT>::value);
  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) {
  assert(0 <= n && n <= 64);
  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 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 id() { return X(0); }
  static constexpr bool commute = true;
};
#line 3 "ds/doubling.hpp"

// 状態 a から 1 回操作すると、状態 b に遷移し、モノイドの元 x を加える。

// 行き先がない場合：-1 （add 不要）

template <typename Monoid, int LOG>
struct Doubling {
  using X = typename Monoid::value_type;
  int N;
  bool is_prepared;
  vvc<int> TO;
  vvc<X> DP;

  Doubling(int N) : N(N), is_prepared(0) {
    TO.assign(LOG, vc<int>(N, -1));
    DP.assign(LOG, vc<X>(N, Monoid::id()));
  }

  void add(int i, int to, X x) {
    assert(!is_prepared);
    assert(-1 <= to && to < N);
    TO[0][i] = to;
    DP[0][i] = x;
  }

  void build() {
    assert(!is_prepared);
    is_prepared = 1;
    FOR(k, LOG - 1) {
      FOR(v, N) {
        int w = TO[k][v];
        if (w == -1) {
          TO[k + 1][v] = -1;
          DP[k + 1][v] = DP[k][v];
          continue;
        }
        TO[k + 1][v] = TO[k][w];
        DP[k + 1][v] = Monoid::op(DP[k][v], DP[k][w]);
      }
    }
  }

  // (to, val)

  pair<int, X> calc(int i, ll step) {
    assert(is_prepared);
    assert(0 <= step && step < (1LL << LOG));
    X x = Monoid::id();
    while (step && i != -1) {
      int k = topbit(step);
      step ^= 1LL << k;
      x = Monoid::op(x, DP[k][i]);
      i = TO[k][i];
    }
    return {i, x};
  }

  // check(to, monoid_sum)

  template <typename F>
  ll max_step(F check, int i) {
    assert(is_prepared);
    X x = Monoid::id();
    ll step = 0;
    assert(check(i, x));
    FOR_R(k, LOG) {
      int j = TO[k][i];
      if (j == -1) continue;
      X y = Monoid::op(x, DP[k][i]);
      if (check(j, y)) {
        step |= 1LL << k;
        i = j;
        x = y;
        assert(i != -1);
      }
    }
    return step;
  }

  void debug() {
    print("TO");
    FOR(k, LOG) print(TO[k]);
    print("DP");
    FOR(k, LOG) print(DP[k]);
  }
};

Back to top page