Disjoint set union, but allows range parallel union (tools/range_parallel_dsu.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2025-08-10 01:57:18+09:00
• Include: #include "tools/range_parallel_dsu.hpp"

Given an undirected graph, it processes the following queries.

• Adding an edge $(a + i, b + i)$ for each $i = 0, 1, \ldots, k - 1$
• Deciding whether given two vertices are in the same connected component

Each connected component internally has a representative vertex.

When two connected components are merged by edge addition, the representative of the larger connected component becomes the representative of the new connected component.

License

• CC0

Author

• anqooqie

Constructor

range_parallel_dsu d(int n);

It creates an undirected graph with $n$ vertices and $0$ edges.

Constraints

• $n \geq 0$

Time Complexity

• $O(n)$

merge (two parameters)

int d.merge(int a, int b);

It adds an edge $(a, b)$.

If the vertices $a$ and $b$ were in the same connected component, it returns the representative of the connected component. Otherwise, the representative of the larger (or former when the two have the same size) connected component becomes the representative of the new connected component, and it returns the new representative.

Constraints

• $0 \leq a < n$
• $0 \leq b < n$

Time Complexity

• $O\left((\log n)^2\right)$ amortized
• $O(n \log n)$ worst

merge (three parameters)

std::vector<std::pair<int, int>> d.merge(int a, int b, int k);

It adds an edge $(a + i, b + i)$ for each $i = 0, 1, \ldots, k - 1$.

Suppose that $m$ merges between different connected components occur as a result of calling this method. Let $s_j$ be the representative with the greater number of elements at the $j$-th merge, and let $t_j$ be the representative with the smaller number of elements. It returns $((s_0, t_0), (s_1, t_1), \ldots, (s_{m - 1}, t_{m - 1}))$.

Constraints

• $0 \leq a \leq a + k \leq n$
• $0 \leq b \leq b + k \leq n$

Time Complexity

• $O\left((\log n)^2\right)$ amortized
• $O(n \log n)$ worst

same

bool d.same(int a, int b);

It returns whether the vertices $a$ and $b$ are in the same connected component.

Constraints

• $0 \leq a < n$
• $0 \leq b < n$

Time Complexity

• $O(1)$

leader

int d.leader(int a);

It returns the representative of the connected component that contains the vertex $a$.

Constraints

• $0 \leq a < n$

Time Complexity

• $O(1)$

size (zero parameters)

int d.size();

It returns $n$.

Constraints

• None

Time Complexity

• $O(1)$

size (one parameter)

int d.size(int a);

It returns the size of the connected component that contains the vertex $a$.

Constraints

• $0 \leq a < n$

Time Complexity

• $O(1)$

groups

std::vector<std::vector<int>> d.groups();

It divides the graph into connected components and returns the list of them.

More precisely, it returns the list of the “list of the vertices in a connected component”. Both of the orders of the connected components and the vertices are undefined.

Constraints

• None

Time Complexity

• $O(n)$

group

std::vector<int> d.group(int a);

It returns the vertices in the connected component that contains the vertex $a$. The order of the vertices is undefined.

Constraints

• None

Time Complexity

• $O(1)$

Depends on

• std::abs(x) extended for my library (tools/abs.hpp)
• $\left\lceil \frac{x}{y} \right\rceil$ (tools/ceil.hpp)
• tools/detail/rolling_hash.hpp
• Extended Euclidean algorithm (tools/extgcd.hpp)
• Floyd's cycle-finding algorithm (tools/find_cycle.hpp)
• $\left\lfloor \frac{x}{y} \right\rfloor$ (tools/floor.hpp)
• std::gcd(m, n) extended for my library (tools/gcd.hpp)
• std::is_arithmetic extended for tools::int128_t and tools::uint128_t (tools/is_arithmetic.hpp)
• std::is_integral extended for tools::int128_t and tools::uint128_t (tools/is_integral.hpp)
• Check whether T is a monoid (tools/is_monoid.hpp)
• std::is_unsigned extended for tools::int128_t and tools::uint128_t (tools/is_unsigned.hpp)
• Minimum non-negative reminder (tools/mod.hpp)
• $\mathbb{Z} / (2^{61} - 1) \mathbb{Z}$ (tools/modint_for_rolling_hash.hpp)
• Typical monoids (tools/monoid.hpp)
• The number of nanoseconds that have elapsed since epoch (tools/now.hpp)
• $b^n$ under a given monoid, and std::pow(b, n) extended for my library (tools/pow.hpp)
• Cache for $b^n \pmod{M}$ (tools/pow_mod_cache.hpp)
• $x^2$ under a given monoid (tools/square.hpp)

Verified with

• tests/range_parallel_dsu.test.cpp

Code

#ifndef TOOLS_RANGE_PARALLEL_DSU_HPP
#define TOOLS_RANGE_PARALLEL_DSU_HPP

#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>
#include <vector>
#include "atcoder/segtree.hpp"
#include "tools/modint_for_rolling_hash.hpp"
#include "tools/now.hpp"
#include "tools/pow_mod_cache.hpp"

namespace tools {
  class range_parallel_dsu {
    using mint = ::tools::modint_for_rolling_hash;
    struct monoid {
      inline static auto pow_b = ::tools::pow_mod_cache<mint>(::tools::now());
      using T = ::std::pair<int, mint>;
      static T op(const T& x, const T& y) {
        return {x.first + y.first, x.second * pow_b[y.first] + y.second};
      }
      static T e() {
        return {0, mint::raw(0)};
      }
    };

    ::atcoder::segtree<typename monoid::T, monoid::op, monoid::e> m_seg;
    ::std::vector<::std::vector<int>> m_groups;

  public:
    range_parallel_dsu() = default;
    explicit range_parallel_dsu(const int n) : m_seg([&]() {
      ::std::vector<typename monoid::T> v(n);
      for (int i = 0; i < n; ++i) {
        v[i] = {1, mint::raw(i + 1)};
      }
      return v;
    }()), m_groups(n) {
      for (int i = 0; i < n; ++i) {
        this->m_groups[i].push_back(i);
      }
    }

    int leader(const int x) const {
      assert(0 <= x && x < this->size());

      return this->m_seg.get(x).second.val() - 1;
    }

    bool same(const int x, const int y) const {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      return this->leader(x) == this->leader(y);
    }

    int merge(int x, int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      x = this->leader(x);
      y = this->leader(y);
      if (x == y) return x;

      if (this->m_groups[x].size() < this->m_groups[y].size()) ::std::swap(x, y);
      ::std::ranges::copy(this->m_groups[y], ::std::back_inserter(this->m_groups[x]));
      for (const auto v : this->m_groups[y]) {
        this->m_seg.set(v, {1, mint::raw(x + 1)});
      }
      this->m_groups[y].clear();

      return x;
    }

    ::std::vector<::std::pair<int, int>> merge(int x, int y, const int k) {
      assert(k >= 0);
      assert(0 <= x && x + k <= this->size());
      assert(0 <= y && y + k <= this->size());

      ::std::vector<::std::pair<int, int>> res;
      int ok = 0;
      int ng = k + 1;
      do {
        while (ng - ok > 1) {
          const auto mid = (ok + ng) / 2;
          if (this->m_seg.prod(x, x + mid).second == this->m_seg.prod(y, y + mid).second) {
            ok = mid;
          } else {
            ng = mid;
          }
        }
        if (ok < k) {
          const auto leader_xor = this->leader(x + ok) ^ this->leader(y + ok);
          const auto new_leader = this->merge(x + ok, y + ok);
          res.emplace_back(new_leader, leader_xor ^ new_leader);
          ++ok;
          ng = k + 1;
        }
      } while (ok < k);

      return res;
    }

    int size() const {
      return this->m_groups.size();
    }

    int size(const int x) const {
      assert(0 <= x && x < this->size());

      return this->m_groups[this->leader(x)].size();
    }

    ::std::vector<::std::vector<int>> groups() const {
      ::std::vector<::std::vector<int>> res(this->size());
      for (int i = 0; i < this->size(); ++i) {
        res[this->leader(i)].push_back(i);
      }
      res.erase(::std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }

    const ::std::vector<int>& group(const int x) const & {
      assert(0 <= x && x < this->size());

      return this->m_groups[this->leader(x)];
    }
    ::std::vector<int> group(const int x) && {
      assert(0 <= x && x < this->size());

      return ::std::move(this->m_groups[this->leader(x)]);
    }
  };
}

#endif

#line 1 "tools/range_parallel_dsu.hpp"



#include <algorithm>
#include <cassert>
#include <iterator>
#include <utility>
#include <vector>
#line 1 "lib/ac-library/atcoder/segtree.hpp"



#line 6 "lib/ac-library/atcoder/segtree.hpp"
#include <functional>
#line 8 "lib/ac-library/atcoder/segtree.hpp"

#line 1 "lib/ac-library/atcoder/internal_bit.hpp"



#ifdef _MSC_VER
#include <intrin.h>
#endif

#if __cplusplus >= 202002L
#include <bit>
#endif

namespace atcoder {

namespace internal {

#if __cplusplus >= 202002L

using std::bit_ceil;

#else

// @return same with std::bit::bit_ceil
unsigned int bit_ceil(unsigned int n) {
    unsigned int x = 1;
    while (x < (unsigned int)(n)) x *= 2;
    return x;
}

#endif

// @param n `1 <= n`
// @return same with std::bit::countr_zero
int countr_zero(unsigned int n) {
#ifdef _MSC_VER
    unsigned long index;
    _BitScanForward(&index, n);
    return index;
#else
    return __builtin_ctz(n);
#endif
}

// @param n `1 <= n`
// @return same with std::bit::countr_zero
constexpr int countr_zero_constexpr(unsigned int n) {
    int x = 0;
    while (!(n & (1 << x))) x++;
    return x;
}

}  // namespace internal

}  // namespace atcoder


#line 10 "lib/ac-library/atcoder/segtree.hpp"

namespace atcoder {

#if __cplusplus >= 201703L

template <class S, auto op, auto e> struct segtree {
    static_assert(std::is_convertible_v<decltype(op), std::function<S(S, S)>>,
                  "op must work as S(S, S)");
    static_assert(std::is_convertible_v<decltype(e), std::function<S()>>,
                  "e must work as S()");

#else

template <class S, S (*op)(S, S), S (*e)()> struct segtree {

#endif

  public:
    segtree() : segtree(0) {}
    explicit segtree(int n) : segtree(std::vector<S>(n, e())) {}
    explicit segtree(const std::vector<S>& v) : _n(int(v.size())) {
        size = (int)internal::bit_ceil((unsigned int)(_n));
        log = internal::countr_zero((unsigned int)size);
        d = std::vector<S>(2 * size, e());
        for (int i = 0; i < _n; i++) d[size + i] = v[i];
        for (int i = size - 1; i >= 1; i--) {
            update(i);
        }
    }

    void set(int p, S x) {
        assert(0 <= p && p < _n);
        p += size;
        d[p] = x;
        for (int i = 1; i <= log; i++) update(p >> i);
    }

    S get(int p) const {
        assert(0 <= p && p < _n);
        return d[p + size];
    }

    S prod(int l, int r) const {
        assert(0 <= l && l <= r && r <= _n);
        S sml = e(), smr = e();
        l += size;
        r += size;

        while (l < r) {
            if (l & 1) sml = op(sml, d[l++]);
            if (r & 1) smr = op(d[--r], smr);
            l >>= 1;
            r >>= 1;
        }
        return op(sml, smr);
    }

    S all_prod() const { return d[1]; }

    template <bool (*f)(S)> int max_right(int l) const {
        return max_right(l, [](S x) { return f(x); });
    }
    template <class F> int max_right(int l, F f) const {
        assert(0 <= l && l <= _n);
        assert(f(e()));
        if (l == _n) return _n;
        l += size;
        S sm = e();
        do {
            while (l % 2 == 0) l >>= 1;
            if (!f(op(sm, d[l]))) {
                while (l < size) {
                    l = (2 * l);
                    if (f(op(sm, d[l]))) {
                        sm = op(sm, d[l]);
                        l++;
                    }
                }
                return l - size;
            }
            sm = op(sm, d[l]);
            l++;
        } while ((l & -l) != l);
        return _n;
    }

    template <bool (*f)(S)> int min_left(int r) const {
        return min_left(r, [](S x) { return f(x); });
    }
    template <class F> int min_left(int r, F f) const {
        assert(0 <= r && r <= _n);
        assert(f(e()));
        if (r == 0) return 0;
        r += size;
        S sm = e();
        do {
            r--;
            while (r > 1 && (r % 2)) r >>= 1;
            if (!f(op(d[r], sm))) {
                while (r < size) {
                    r = (2 * r + 1);
                    if (f(op(d[r], sm))) {
                        sm = op(d[r], sm);
                        r--;
                    }
                }
                return r + 1 - size;
            }
            sm = op(d[r], sm);
        } while ((r & -r) != r);
        return 0;
    }

  private:
    int _n, size, log;
    std::vector<S> d;

    void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); }
};

}  // namespace atcoder


#line 1 "tools/modint_for_rolling_hash.hpp"



#line 1 "tools/detail/rolling_hash.hpp"



#include <cstdint>
#line 6 "tools/detail/rolling_hash.hpp"
#include <tuple>
#line 1 "tools/pow.hpp"



#include <type_traits>
#line 6 "tools/pow.hpp"
#include <cmath>
#line 1 "tools/monoid.hpp"



#line 6 "tools/monoid.hpp"
#include <cstddef>
#include <limits>
#line 1 "tools/gcd.hpp"



#include <numeric>
#line 6 "tools/gcd.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::std::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool>
    && ::std::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>
  )
  constexpr ::std::common_type_t<M, N> gcd(const M m, const N n) {
    return ::std::gcd(m, n);
  }
}


#line 1 "tools/is_arithmetic.hpp"



#line 5 "tools/is_arithmetic.hpp"

namespace tools {
  template <typename T>
  struct is_arithmetic : ::std::is_arithmetic<T> {};

  template <typename T>
  inline constexpr bool is_arithmetic_v = ::tools::is_arithmetic<T>::value;
}


#line 1 "tools/is_integral.hpp"



#line 5 "tools/is_integral.hpp"

namespace tools {
  template <typename T>
  struct is_integral : ::std::is_integral<T> {};

  template <typename T>
  inline constexpr bool is_integral_v = ::tools::is_integral<T>::value;
}


#line 12 "tools/monoid.hpp"

namespace tools {
  namespace monoid {
    template <typename M>
    class bit_and {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return x & y;
      }
      static T e() {
        return ::std::numeric_limits<T>::max();
      }
    };

    template <typename M>
    class bit_or {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return x | y;
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M> requires (!::tools::is_arithmetic_v<M> || (::tools::is_integral_v<M> && !::std::is_same_v<M, bool>))
    class gcd {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return ::tools::gcd(x, y);
      }
      static T e() {
        return T(0);
      }
    };

    template <typename M, M ...dummy>
    class max;

    template <typename M> requires (::tools::is_arithmetic_v<M>)
    class max<M> {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return ::std::max(x, y);
      }
      static T e() {
        if constexpr (::tools::is_integral_v<M>) {
          return ::std::numeric_limits<M>::min();
        } else {
          return -::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    class max<M, E> {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        assert(E <= x);
        assert(E <= y);
        return ::std::max(x, y);
      }
      static T e() {
        return E;
      }
    };

    template <typename M, M ...dummy>
    class min;

    template <typename M> requires (::tools::is_arithmetic_v<M>)
    class min<M> {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return ::std::min(x, y);
      }
      static T e() {
        if constexpr (::tools::is_integral_v<M>) {
          return ::std::numeric_limits<M>::max();
        } else {
          return ::std::numeric_limits<M>::infinity();
        }
      }
    };

    template <typename M, M E>
    class min<M, E> {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        assert(x <= E);
        assert(y <= E);
        return ::std::min(x, y);
      }
      static T e() {
        return E;
      }
    };

    template <typename M>
    class multiplies {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return x * y;
      }
      static T e() {
        return T(1);
      }
    };

    template <>
    struct multiplies<bool> {
      using T = bool;
      static T op(const bool x, const bool y) {
        return x && y;
      }
      static T e() {
        return true;
      }
    };

    template <typename M, M E>
    class update {
      using VR = ::std::conditional_t<::tools::is_arithmetic_v<M> && sizeof(M) <= sizeof(::std::size_t), const M, const M&>;

    public:
      using T = M;
      static T op(VR x, VR y) {
        return x == E ? y : x;
      }
      static T e() {
        return E;
      }
    };
  }
}


#line 1 "tools/square.hpp"



#line 1 "tools/is_monoid.hpp"



#line 6 "tools/is_monoid.hpp"

namespace tools {

  template <typename M, typename = void>
  struct is_monoid : ::std::false_type {};

  template <typename M>
  struct is_monoid<M, ::std::enable_if_t<
    ::std::is_same_v<typename M::T, decltype(M::op(::std::declval<typename M::T>(), ::std::declval<typename M::T>()))> &&
    ::std::is_same_v<typename M::T, decltype(M::e())>
  , void>> : ::std::true_type {};

  template <typename M>
  inline constexpr bool is_monoid_v = ::tools::is_monoid<M>::value;
}


#line 6 "tools/square.hpp"

namespace tools {

  template <typename M>
  ::std::enable_if_t<::tools::is_monoid_v<M>, typename M::T> square(const typename M::T& x) {
    return M::op(x, x);
  }

  template <typename T>
  ::std::enable_if_t<!::tools::is_monoid_v<T>, T> square(const T& x) {
    return x * x;
  }
}


#line 9 "tools/pow.hpp"

namespace tools {

  template <typename M, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, typename M::T> pow(const typename M::T& base, const E exponent) {
    assert(exponent >= 0);
    return exponent == 0
      ? M::e()
      : exponent % 2 == 0
        ? ::tools::square<M>(::tools::pow<M>(base, exponent / 2))
        : M::op(::tools::pow<M>(base, exponent - 1), base);
  }

  template <typename T, typename E>
  ::std::enable_if_t<::std::is_integral_v<E>, T> pow(const T& base, const E exponent) {
    assert(exponent >= 0);
    return ::tools::pow<::tools::monoid::multiplies<T>>(base, exponent);
  }

  template <typename T, typename E>
  auto pow(const T base, const E exponent) -> ::std::enable_if_t<!::std::is_integral_v<E>, decltype(::std::pow(base, exponent))> {
    return ::std::pow(base, exponent);
  }
}


#line 1 "tools/extgcd.hpp"



#line 1 "tools/abs.hpp"



namespace tools {
  constexpr float abs(const float x) {
    return x < 0 ? -x : x;
  }
  constexpr double abs(const double x) {
    return x < 0 ? -x : x;
  }
  constexpr long double abs(const long double x) {
    return x < 0 ? -x : x;
  }
  constexpr int abs(const int x) {
    return x < 0 ? -x : x;
  }
  constexpr long abs(const long x) {
    return x < 0 ? -x : x;
  }
  constexpr long long abs(const long long x) {
    return x < 0 ? -x : x;
  }
  constexpr unsigned int abs(const unsigned int x) noexcept {
    return x;
  }
  constexpr unsigned long abs(const unsigned long x) noexcept {
    return x;
  }
  constexpr unsigned long long abs(const unsigned long long x) noexcept {
    return x;
  }
}


#line 9 "tools/extgcd.hpp"

namespace tools {

  template <typename T>
  ::std::tuple<T, T, T> extgcd(T prev_r, T r) {
    const bool prev_r_is_neg = prev_r < T(0);
    const bool r_is_neg = r < T(0);

    if (prev_r_is_neg) prev_r = -prev_r;
    if (r_is_neg) r = -r;

    #ifndef NDEBUG
    const T a = prev_r;
    const T b = r;
    #endif

    T prev_s(1);
    T prev_t(0);
    T s(0);
    T t(1);
    while (r != T(0)) {
      const T q = prev_r / r;
      ::std::tie(prev_r, r) = ::std::make_pair(r, prev_r - q * r);
      ::std::tie(prev_s, s) = ::std::make_pair(s, prev_s - q * s);
      ::std::tie(prev_t, t) = ::std::make_pair(t, prev_t - q * t);
    }

    if (prev_r_is_neg) prev_s = -prev_s;
    if (r_is_neg) prev_t = -prev_t;

    assert(::tools::abs(prev_s) <= ::std::max(b / prev_r / T(2), T(1)));
    assert(::tools::abs(prev_t) <= ::std::max(a / prev_r / T(2), T(1)));
    return ::std::make_tuple(prev_s, prev_t, prev_r);
  }
}


#line 1 "tools/pow_mod_cache.hpp"



#line 5 "tools/pow_mod_cache.hpp"
#include <optional>
#line 1 "tools/find_cycle.hpp"



#line 5 "tools/find_cycle.hpp"

namespace tools {

  template <typename T, typename F>
  ::std::pair<long long, long long> find_cycle(const T& seed, const F& f) {
    auto i = 1LL;
    auto j = 2LL;
    T x = f(seed);
    T y = f(f(seed));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    i = 0;
    x = seed;
    for (; x != y; ++i, ++j, x = f(x), y = f(y));

    const auto head = i;

    ++i;
    j = i + 1;
    x = f(x);
    y = f(f(y));
    for (; x != y; ++i, j += 2, x = f(x), y = f(f(y)));

    const auto cycle = j - i;

    return ::std::make_pair(head, cycle);
  }
}


#line 1 "tools/mod.hpp"



#line 7 "tools/mod.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> mod(const M a, const N b) noexcept {
    assert(b != 0);

    using UM = ::std::make_unsigned_t<M>;
    using UN = ::std::make_unsigned_t<N>;
    const UM ua = a >= 0 ? a : static_cast<UM>(-(a + 1)) + 1;
    const UN ub = b >= 0 ? b : static_cast<UN>(-(b + 1)) + 1;
    auto r = ua % ub;
    if (a < 0 && r > 0) {
      r = ub - r;
    }
    return r;
  }
}


#line 1 "tools/floor.hpp"



#line 7 "tools/floor.hpp"

namespace tools {

  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> floor(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x >= 0) {
        return x / y;
      } else {
        return (x + 1) / y - 1;
      }
    } else {
      if (x > 0) {
        return (x - 1) / y - 1;
      } else {
        return x / y;
      }
    }
  }
}


#line 1 "tools/ceil.hpp"



#line 1 "tools/is_unsigned.hpp"



#line 5 "tools/is_unsigned.hpp"

namespace tools {
  template <typename T>
  struct is_unsigned : ::std::is_unsigned<T> {};

  template <typename T>
  inline constexpr bool is_unsigned_v = ::tools::is_unsigned<T>::value;
}


#line 8 "tools/ceil.hpp"

namespace tools {
  template <typename M, typename N> requires (
    ::tools::is_integral_v<M> && !::std::is_same_v<::std::remove_cv_t<M>, bool> &&
    ::tools::is_integral_v<N> && !::std::is_same_v<::std::remove_cv_t<N>, bool>)
  constexpr ::std::common_type_t<M, N> ceil(const M x, const N y) noexcept {
    assert(y != 0);
    if (y >= 0) {
      if (x > 0) {
        return (x - 1) / y + 1;
      } else {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      }
    } else {
      if (x >= 0) {
        if constexpr (::tools::is_unsigned_v<::std::common_type_t<M, N>>) {
          return 0;
        } else {
          return x / y;
        }
      } else {
        return (x + 1) / y + 1;
      }
    }
  }
}


#line 16 "tools/pow_mod_cache.hpp"

namespace tools {

  template <class M>
  class pow_mod_cache {
    ::std::vector<M> m_pow;
    ::std::vector<M> m_cumsum;
    ::std::vector<M> m_inv_pow;
    ::std::vector<M> m_inv_cumsum;
    ::std::optional<::std::pair<long long, long long>> m_period;

  public:
    pow_mod_cache() = default;
    explicit pow_mod_cache(const M base) : m_pow({M(1), base}), m_cumsum({M::raw(0)}), m_inv_pow({M(1)}), m_inv_cumsum({M::raw(0)}) {
      if (base == M(-1)) {
        if (M::mod() > 2) {
          this->m_period = ::std::make_pair(0LL, 2LL);
        } else {
          this->m_period = ::std::make_pair(0LL, 1LL);
          this->m_pow.resize(1);
        }
        this->m_inv_pow.clear();
        this->m_inv_cumsum.clear();
      }
    }
    template <typename Z, ::std::enable_if_t<::std::is_integral_v<Z>, ::std::nullptr_t> = nullptr>
    explicit pow_mod_cache(const Z base) : pow_mod_cache(M(base)) {
    }

    M operator[](const long long n) {
      if (!this->m_period) {
        if (::std::max<long long>(::std::ssize(this->m_pow) - 1, n) - ::std::min<long long>(n, -(::std::ssize(this->m_inv_pow) - 1)) + 1 < M::mod() - 1) {
          if (n >= 0) {
            const long long size = ::std::ssize(this->m_pow);
            this->m_pow.resize(::std::max(size, n + 1));
            for (long long i = size; i < ::std::ssize(this->m_pow); ++i) {
              this->m_pow[i] = this->m_pow[i - 1] * this->m_pow[1];
            }
            return this->m_pow[n];
          } else {
            if (this->m_inv_pow.size() == 1) {
              this->m_inv_pow.push_back(this->m_pow[1].inv());
            }
            const long long size = ::std::ssize(this->m_inv_pow);
            this->m_inv_pow.resize(::std::max(size, -n + 1));
            for (long long i = size; i < ::std::ssize(this->m_inv_pow); ++i) {
              this->m_inv_pow[i] = this->m_inv_pow[i - 1] * this->m_inv_pow[1];
            }
            return this->m_inv_pow[-n];
          }
        }

        this->m_period = ::tools::find_cycle(this->m_pow[0], [&](const M& prev) { return prev * this->m_pow[1]; });
        const long long size = ::std::ssize(this->m_pow);
        this->m_pow.resize(this->m_period->first + this->m_period->second);
        for (long long i = size; i < ::std::ssize(this->m_pow); ++i) {
          this->m_pow[i] = this->m_pow[i - 1] * this->m_pow[1];
        }
        this->m_inv_pow.clear();
        this->m_inv_cumsum.clear();
      }

      if (this->m_period->first == 0) {
        return this->m_pow[::tools::mod(n, this->m_period->second)];
      } else {
        assert(n >= 0);
        if (n < this->m_period->first + this->m_period->second) {
          return this->m_pow[n];
        } else {
          return this->m_pow[(n - this->m_period->first) % this->m_period->second + this->m_period->first];
        }
      }
    }

    M sum(const long long l, const long long r) {
      if (l >= r) return M::raw(0);

      (*this)[r - 1];
      (*this)[l];

      {
        const long long size = ::std::ssize(this->m_cumsum);
        this->m_cumsum.resize(this->m_pow.size() + 1);
        for (long long i = size; i < ::std::ssize(this->m_cumsum); ++i) {
          this->m_cumsum[i] = this->m_cumsum[i - 1] + this->m_pow[i - 1];
        }
      }

      if (!this->m_period) {
        const long long size = ::std::ssize(this->m_inv_cumsum);
        this->m_inv_cumsum.resize(this->m_inv_pow.size() + 1);
        for (long long i = size; i < ::std::ssize(this->m_inv_cumsum); ++i) {
          this->m_inv_cumsum[i] = this->m_inv_cumsum[i - 1] + this->m_pow[i - 1];
        }

        if (l >= 0) {
          return this->m_cumsum[r] - this->m_cumsum[l];
        } else if (r <= 0) {
          return this->m_inv_cumsum[-l] - this->m_inv_cumsum[-r];
        } else {
          return (this->m_inv_cumsum[-l] - this->m_inv_cumsum[1]) + (this->m_cumsum[r] - this->m_cumsum[0]);
        }
      }

      static const auto cumsum = [&](const long long ll, const long long rr) {
        return this->m_cumsum[rr] - this->m_cumsum[ll];
      };

      if (l >= 0) {
        static const auto f = [&](const long long x) {
          if (x <= this->m_period->first + this->m_period->second) {
            return cumsum(0, x);
          } else {
            return cumsum(0, this->m_period->first) +
              cumsum(this->m_period->first, this->m_period->first + this->m_period->second) * ((x - this->m_period->first) / this->m_period->second) +
              cumsum(this->m_period->first, (x - this->m_period->first) % this->m_period->second + this->m_period->first);
          }
        };
        return f(r) - f(l);
      } else {
        const auto& n = this->m_period->second;
        return cumsum(::tools::mod(l, n), n) + cumsum(0, ::tools::mod(r, n)) + cumsum(0, n) * M(::tools::floor(r, n) - ::tools::ceil(l, n));
      }
    }
  };
}


#line 1 "tools/now.hpp"



#include <chrono>

namespace tools {
  inline long long now() {
    return ::std::chrono::duration_cast<::std::chrono::nanoseconds>(::std::chrono::high_resolution_clock::now().time_since_epoch()).count();
  }
}


#line 12 "tools/detail/rolling_hash.hpp"

namespace tools {
  class rolling_hash;

  class modint_for_rolling_hash {
  private:
    static constexpr ::std::uint64_t MASK30 = (::std::uint64_t(1) << 30) - 1;
    static constexpr ::std::uint64_t MASK31 = (::std::uint64_t(1) << 31) - 1;
    static constexpr ::std::uint64_t MOD = (::std::uint64_t(1) << 61) - 1;
    static constexpr ::std::uint64_t MASK61 = MOD;
    static constexpr ::std::uint64_t POSITIVIZER = MOD * 4;

    ::std::uint64_t m_val;

    modint_for_rolling_hash(const ::std::uint64_t x, int) : m_val(x) {
    }

    static ::std::uint64_t mul(const ::std::uint64_t a, const ::std::uint64_t b) {
      assert(a < MOD);
      assert(b < MOD);
      const ::std::uint64_t au = a >> 31;
      const ::std::uint64_t ad = a & MASK31;
      const ::std::uint64_t bu = b >> 31;
      const ::std::uint64_t bd = b & MASK31;
      const ::std::uint64_t mid = ad * bu + au * bd;
      const ::std::uint64_t midu = mid >> 30;
      const ::std::uint64_t midd = mid & MASK30;
      return au * bu * 2 + midu + (midd << 31) + ad * bd;
    }
    static ::std::uint64_t calc_mod(const ::std::uint64_t x) {
      const ::std::uint64_t xu = x >> 61;
      const ::std::uint64_t xd = x & MASK61;
      ::std::uint64_t res = xu + xd;
      if (res >= MOD) res -= MOD;
      return res;
    }

  public:
    modint_for_rolling_hash() = default;
    modint_for_rolling_hash(const ::tools::modint_for_rolling_hash&) = default;
    modint_for_rolling_hash(::tools::modint_for_rolling_hash&&) = default;
    ~modint_for_rolling_hash() = default;
    ::tools::modint_for_rolling_hash& operator=(const ::tools::modint_for_rolling_hash&) = default;
    ::tools::modint_for_rolling_hash& operator=(::tools::modint_for_rolling_hash&&) = default;

    explicit modint_for_rolling_hash(const ::std::uint64_t x) : m_val(calc_mod(x)) {
    }

    ::tools::modint_for_rolling_hash pow(const long long n) const {
      return ::tools::pow(*this, n);
    }
    ::tools::modint_for_rolling_hash inv() const {
      assert(this->m_val != 0);
      return ::tools::modint_for_rolling_hash(::std::get<0>(::tools::extgcd(this->m_val, MOD)));
    }

    ::tools::modint_for_rolling_hash operator+() const {
      return *this;
    }
    ::tools::modint_for_rolling_hash operator-() const {
      return ::tools::modint_for_rolling_hash(POSITIVIZER - this->m_val);
    }
    friend ::tools::modint_for_rolling_hash operator+(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(lhs.m_val + rhs.m_val);
    }
    ::tools::modint_for_rolling_hash& operator+=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(this->m_val + other.m_val);
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator-(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(lhs.m_val + POSITIVIZER - rhs.m_val);
    }
    ::tools::modint_for_rolling_hash& operator-=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(this->m_val + POSITIVIZER - other.m_val);
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator*(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(mul(lhs.m_val, rhs.m_val));
    }
    ::tools::modint_for_rolling_hash& operator*=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(mul(this->m_val, other.m_val));
      return *this;
    }
    friend ::tools::modint_for_rolling_hash operator/(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return ::tools::modint_for_rolling_hash(mul(lhs.m_val, rhs.inv().m_val));
    }
    ::tools::modint_for_rolling_hash& operator/=(const ::tools::modint_for_rolling_hash& other) {
      this->m_val = calc_mod(mul(this->m_val, other.inv().m_val));
      return *this;
    }
    ::tools::modint_for_rolling_hash& operator++() {
      this->m_val = calc_mod(this->m_val + 1);
      return *this;
    }
    ::tools::modint_for_rolling_hash operator++(int) {
      const auto result = *this;
      ++(*this);
      return result;
    }
    ::tools::modint_for_rolling_hash& operator--() {
      this->m_val = calc_mod(this->m_val + POSITIVIZER - 1);
      return *this;
    }
    ::tools::modint_for_rolling_hash operator--(int) {
      const auto result = *this;
      --(*this);
      return result;
    }

    friend bool operator==(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return lhs.m_val == rhs.m_val;
    }
    friend bool operator!=(const ::tools::modint_for_rolling_hash& lhs, const ::tools::modint_for_rolling_hash& rhs) {
      return lhs.m_val != rhs.m_val;
    }

    long long val() const {
      return this->m_val;
    }

    static ::tools::modint_for_rolling_hash raw(const ::std::uint64_t x) {
      return ::tools::modint_for_rolling_hash(x, 0);
    }
    static long long mod() {
      return MOD;
    }

    friend ::tools::rolling_hash;
  };

  class rolling_hash {
  private:
    using mint = ::tools::modint_for_rolling_hash;
    inline static ::tools::pow_mod_cache<mint> m_pow_base = ::tools::pow_mod_cache<mint>(::tools::now());
    ::std::vector<mint> m_hash;

  public:
    rolling_hash() = default;
    rolling_hash(const ::tools::rolling_hash&) = default;
    rolling_hash(::tools::rolling_hash&&) = default;
    ~rolling_hash() = default;
    ::tools::rolling_hash& operator=(const ::tools::rolling_hash&) = default;
    ::tools::rolling_hash& operator=(::tools::rolling_hash&&) = default;

    template <typename InputIterator>
    rolling_hash(InputIterator begin, InputIterator end) {
      this->m_hash.push_back(mint::raw(0));
      const auto base = m_pow_base[1].m_val;
      for (auto it = begin; it != end; ++it) {
        this->m_hash.emplace_back(mint::mul(this->m_hash.back().m_val, base) + *it);
      }
      m_pow_base[this->m_hash.size()];
    }

    mint pow_base(const ::std::size_t i) const {
      return m_pow_base[i];
    }

    mint slice(const ::std::size_t l, const ::std::size_t r) const {
      assert(l <= r && r <= this->m_hash.size());
      return mint(this->m_hash[r].m_val + mint::POSITIVIZER - mint::mul(this->m_hash[l].m_val, m_pow_base[r - l].m_val));
    }
  };
}


#line 5 "tools/modint_for_rolling_hash.hpp"


#line 13 "tools/range_parallel_dsu.hpp"

namespace tools {
  class range_parallel_dsu {
    using mint = ::tools::modint_for_rolling_hash;
    struct monoid {
      inline static auto pow_b = ::tools::pow_mod_cache<mint>(::tools::now());
      using T = ::std::pair<int, mint>;
      static T op(const T& x, const T& y) {
        return {x.first + y.first, x.second * pow_b[y.first] + y.second};
      }
      static T e() {
        return {0, mint::raw(0)};
      }
    };

    ::atcoder::segtree<typename monoid::T, monoid::op, monoid::e> m_seg;
    ::std::vector<::std::vector<int>> m_groups;

  public:
    range_parallel_dsu() = default;
    explicit range_parallel_dsu(const int n) : m_seg([&]() {
      ::std::vector<typename monoid::T> v(n);
      for (int i = 0; i < n; ++i) {
        v[i] = {1, mint::raw(i + 1)};
      }
      return v;
    }()), m_groups(n) {
      for (int i = 0; i < n; ++i) {
        this->m_groups[i].push_back(i);
      }
    }

    int leader(const int x) const {
      assert(0 <= x && x < this->size());

      return this->m_seg.get(x).second.val() - 1;
    }

    bool same(const int x, const int y) const {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      return this->leader(x) == this->leader(y);
    }

    int merge(int x, int y) {
      assert(0 <= x && x < this->size());
      assert(0 <= y && y < this->size());

      x = this->leader(x);
      y = this->leader(y);
      if (x == y) return x;

      if (this->m_groups[x].size() < this->m_groups[y].size()) ::std::swap(x, y);
      ::std::ranges::copy(this->m_groups[y], ::std::back_inserter(this->m_groups[x]));
      for (const auto v : this->m_groups[y]) {
        this->m_seg.set(v, {1, mint::raw(x + 1)});
      }
      this->m_groups[y].clear();

      return x;
    }

    ::std::vector<::std::pair<int, int>> merge(int x, int y, const int k) {
      assert(k >= 0);
      assert(0 <= x && x + k <= this->size());
      assert(0 <= y && y + k <= this->size());

      ::std::vector<::std::pair<int, int>> res;
      int ok = 0;
      int ng = k + 1;
      do {
        while (ng - ok > 1) {
          const auto mid = (ok + ng) / 2;
          if (this->m_seg.prod(x, x + mid).second == this->m_seg.prod(y, y + mid).second) {
            ok = mid;
          } else {
            ng = mid;
          }
        }
        if (ok < k) {
          const auto leader_xor = this->leader(x + ok) ^ this->leader(y + ok);
          const auto new_leader = this->merge(x + ok, y + ok);
          res.emplace_back(new_leader, leader_xor ^ new_leader);
          ++ok;
          ng = k + 1;
        }
      } while (ok < k);

      return res;
    }

    int size() const {
      return this->m_groups.size();
    }

    int size(const int x) const {
      assert(0 <= x && x < this->size());

      return this->m_groups[this->leader(x)].size();
    }

    ::std::vector<::std::vector<int>> groups() const {
      ::std::vector<::std::vector<int>> res(this->size());
      for (int i = 0; i < this->size(); ++i) {
        res[this->leader(i)].push_back(i);
      }
      res.erase(::std::remove_if(res.begin(), res.end(), [](const auto& group) { return group.empty(); }), res.end());
      return res;
    }

    const ::std::vector<int>& group(const int x) const & {
      assert(0 <= x && x < this->size());

      return this->m_groups[this->leader(x)];
    }
    ::std::vector<int> group(const int x) && {
      assert(0 <= x && x < this->size());

      return ::std::move(this->m_groups[this->leader(x)]);
    }
  };
}

Back to top page