kpr/data_structure/data_structure.hpp

View this file on GitHub
Last update: 2023-06-22 14:29:46+09:00
Include: #include "kpr/data_structure/data_structure.hpp"

Depends on

Required by

kpr/all.hpp

Code

#pragma once
#include "FenwickTree.hpp"
#include "SegmentTree.hpp"
#include "UnionFind.hpp"
#include "WeightedUnionFind.hpp"

#line 2 "kpr/data_structure/FenwickTree.hpp"
#include <cstddef>
#include <utility>
#include <vector>
#line 2 "kpr/function/monoid.hpp"
#include <limits>
#include <type_traits>
#line 2 "kpr/meta/setting.hpp"
#include <cstdint>

#ifndef KYOPRO_BASE_INT
// 基本符号付き整数型

#define KYOPRO_BASE_INT std::int64_t
#endif

#ifndef KYOPRO_BASE_UINT
// 基本符号なし整数型

#define KYOPRO_BASE_UINT std::uint64_t
#endif

#ifndef KYOPRO_BASE_FLOAT
// 基本浮動小数点数型

#define KYOPRO_BASE_FLOAT double
#endif

#ifndef KYOPRO_LL
// ll

#define KYOPRO_LL long long
#endif

#ifndef KYOPRO_LF
// lf

#define KYOPRO_LF double
#endif

#ifndef KYOPRO_MINT
// mint

#define KYOPRO_MINT kpr::ModInt<mod>
#endif

#ifndef KYOPRO_DEFAULT_MOD
// 問題で設定されたmod

#define KYOPRO_DEFAULT_MOD (static_cast<KYOPRO_BASE_UINT>(998244353))
#endif

#ifndef KYOPRO_DECIMAL_PRECISION
// 小数精度(桁)

#define KYOPRO_DECIMAL_PRECISION (static_cast<KYOPRO_BASE_UINT>(12))
#endif

#ifndef KYOPRO_INF_DIV
// 無限大を表す整数が最大値の何分の一かを表す

#define KYOPRO_INF_DIV (static_cast<KYOPRO_BASE_UINT>(3))
#endif

#ifndef KYOPRO_BUFFER_SIZE
// デフォルトのバッファサイズ

#define KYOPRO_BUFFER_SIZE (static_cast<KYOPRO_BASE_UINT>(2048))
#endif

#ifndef KYOPRO_BINOM_MOD_MAX
// デフォルトのBinomModの計算上限

#define KYOPRO_BINOM_MOD_MAX (static_cast<KYOPRO_BASE_UINT>(1000000))
#endif
#line 3 "kpr/meta/trait.hpp"
#include <iterator>
#include <tuple>
#line 7 "kpr/meta/trait.hpp"

namespace kpr {
    namespace helper {
        template<class T>
        struct is_integer_helper {
            static constexpr bool value = std::is_integral_v<T>;
        };

        #ifdef __SIZEOF_INT128__
        template<>
        struct is_integer_helper<__int128_t> {
            static constexpr bool value = true;
        };
        template<>
        struct is_integer_helper<__uint128_t> {
            static constexpr bool value = true;
        };
        #endif
    } // namespace helper


    // 型Tが整数か調べる

    template<class T>
    struct is_integer {
        static constexpr bool value = helper::is_integer_helper<std::remove_cv_t<T>>::value;
    };
    // 型Tが整数か調べる

    template<class T>
    inline constexpr bool is_integer_v = is_integer<T>::value;

    // 型Tが符号付き整数か調べる

    template<class T>
    struct is_signed_integer {
        static constexpr bool value = is_integer_v<T> && std::is_signed_v<T>;
    };
    // 型Tが符号付き整数か調べる

    template<class T>
    inline constexpr bool is_signed_integer_v = is_signed_integer<T>::value;

    // 型Tが符号無し整数か調べる

    template<class T>
    struct is_unsigned_integer {
        static constexpr bool value = is_integer_v<T> && !std::is_signed_v<T>;
    };
    // 型Tが符号無し整数か調べる

    template<class T>
    inline constexpr bool is_unsigned_integer_v = is_unsigned_integer<T>::value;

    namespace helper {
        template<class T>
        struct is_floating_point_helper {
            static constexpr bool value = std::is_floating_point_v<T>;
        };

        #ifdef __SIZEOF_FLOAT128__
        template<>
        struct is_floating_point_helper<__float128> {
            static constexpr bool value = true;
        };
        #endif
    } // namespace helper


    // 型Tが浮動小数点数か調べる

    template<class T>
    struct is_floating_point {
        static constexpr bool value = helper::is_floating_point_helper<std::remove_cv_t<T>>::value;
    };
    // 型Tが浮動小数点数か調べる

    template<class T>
    inline constexpr bool is_floating_point_v = is_floating_point<T>::value;

    // 型Tが算術型か調べる

    template<class T>
    struct is_arithmetic {
        static constexpr bool value = is_integer_v<T> || is_floating_point_v<T>;
    };
    // 型Tが算術型か調べる

    template<class T>
    inline constexpr bool is_arithmetic_v = is_arithmetic<T>::value;

    // 型Tがスカラーか調べる

    template<class T>
    struct is_scalar {
        static constexpr bool value = is_arithmetic_v<T> || std::is_enum_v<T> || std::is_pointer_v<T> || std::is_member_pointer_v<T> || std::is_null_pointer_v<T>;
    };
    // 型Tがスカラーか調べる

    template<class T>
    inline constexpr bool is_scalar_v = is_scalar<T>::value;

    // size以上の大きさを持つ最小の符号付き整数を調べる

    template<std::size_t size>
    struct int_least {
    private:
        static constexpr auto get_type() noexcept {
            static_assert(size <= 128, "The given integer type is too large");
            if constexpr (size <= 8) return std::int_least8_t{};
            else if constexpr (size <= 16) return std::int_least16_t{};
            else if constexpr (size <= 32) return std::int_least32_t{};
            else if constexpr (size <= 64) return std::int_least64_t{};
            else return __int128_t{};
        }

    public:
        using type = decltype(get_type());
    };
    // size以上の大きさを持つ最小の符号付き整数を調べる

    template<std::size_t size>
    using int_least_t = typename int_least<size>::type;

    // size以上の大きさを持つ最小の符号無し整数を調べる

    template<std::size_t size>
    struct uint_least {
    private:
        static constexpr auto get_type() noexcept {
            static_assert(size <= 128, "The give integer type is too large");
            if constexpr (size <= 8) return std::uint_least8_t{};
            else if constexpr (size <= 16) return std::uint_least16_t{};
            else if constexpr (size <= 32) return std::uint_least32_t{};
            else if constexpr (size <= 64) return std::uint_least64_t{};
            else return __uint128_t{};
        }

    public:
        using type = decltype(get_type());
    };
    // size以上の大きさを持つ最小の符号無し整数を調べる

    template<std::size_t size>
    using uint_least_t = typename uint_least<size>::type;

    // Tの次に大きい整数型を調べる

    template<class T>
    struct next_integer {
        static_assert(is_integer_v<T>, "The given type must be an integer type");
        static_assert(sizeof(T) <= 8, "The given integer type is too large");
        using type = std::conditional_t<std::is_signed_v<T>, int_least_t<sizeof(T) * 16>, uint_least_t<sizeof(T) * 16>>;
    };
    // Tの次に大きい整数型を調べる

    template<class T>
    using next_integer_t = typename next_integer<T>::type;

    // Tの次に小さい整数型を調べる

    template<class T>
    struct prev_integer {
        static_assert(is_integer_v<T>, "The given type must be an integer type");
        static_assert(sizeof(T) >= 2, "The given integer type is too large");
        using type = std::conditional_t<std::is_signed_v<T>, int_least_t<sizeof(T) * 4>, uint_least_t<sizeof(T) * 4>>;
    };
    // Tの次に小さい整数型を調べる

    template<class T>
    using prev_integer_t = typename prev_integer<T>::type;

    // 型Tがイテレータか調べる

    template<class T, class = void>
    struct is_iterator {
        static constexpr bool value = false;
    };
    template<class T>
    struct is_iterator<T, std::void_t<typename std::iterator_traits<T>::iterator_category>> {
        static constexpr bool value = true;
    };
    // 型Tがイテレータか調べる

    template<class T>
    inline constexpr bool is_iterator_v = is_iterator<T>::value;

    // 型TがRangeか調べる

    template<class T, class = void>
    struct is_range {
        static constexpr bool value = false;
    };
    template<class T>
    struct is_range<T, std::void_t<decltype(std::begin(std::declval<std::add_lvalue_reference_t<T>>()), std::end(std::declval<std::add_lvalue_reference_t<T>>()))>> {
        static constexpr bool value = true;
    };
     // 型TがRangeか調べる

    template<class T>
    inline constexpr bool is_range_v = is_range<T>::value;

    // Range型Tからイテレータの型を調べる

    template<class T>
    struct range_iterator {
        using type = std::decay_t<decltype(std::begin(std::declval<T>()))>;
    };
    // Range型Tからイテレータの型を調べる

    template<class T>
    using range_iterator_t = typename range_iterator<T>::type;

    // Range型Tから読み取り専用イテレータの型を調べる

    template<class T>
    struct range_const_iterator {
        using type = std::decay_t<decltype(std::cbegin(std::declval<T>()))>;
    };
    // Range型Tから読み取り専用イテレータの型を調べる

    template<class T>
    using range_const_iterator_t = typename range_iterator<T>::type;

    // Range型Tから要素の型を調べる

    template<class T>
    struct range_value {
        using type = std::decay_t<decltype(*std::begin(std::declval<T>()))>;
    };
    // Range型Tから要素の型を調べる

    template<class T>
    using range_value_t = typename range_value<T>::type;
} // namespace kpr

#line 6 "kpr/function/monoid.hpp"

namespace kpr {
    // 足し算のmonoid

    template<class T>
    struct Add {
        using value_type = T;

        static constexpr T id() noexcept {
            return T{};
        }

        constexpr T operator ()(const T& a, const T& b) const noexcept {
            return a + b;
        }

        static constexpr T inv(const T& a) noexcept {
            return -a;
        }
    };

    // 掛け算のmonoid

    template<class T>
    struct Mul {
        using value_type = T;

        static constexpr T id() noexcept {
            return 1;
        }

        constexpr T operator ()(const T& a, const T& b) const noexcept {
            return a * b;
        }

        static constexpr T inv(const T& a) noexcept {
            return 1 / a;
        }
    };

    // minのmonoid

    template<class T>
    struct Min {
        using value_type = T;

        static constexpr T id() noexcept {
            if constexpr (std::numeric_limits<T>::has_infinity) return std::numeric_limits<T>::infinity();
            return std::numeric_limits<T>::max() / KYOPRO_INF_DIV;
        }

        constexpr T operator ()(const T& a, const T& b) const noexcept {
            return a < b ? a : b;
        }
    };

    // maxのmonoid

    template<class T>
    struct Max {
        using value_type = T;

        static constexpr T id() noexcept {
            if constexpr (std::numeric_limits<T>::has_infinity) return -std::numeric_limits<T>::infinity();
            if constexpr (std::is_signed_v<T>) return -(std::numeric_limits<T>::max() / KYOPRO_INF_DIV);
            return 0;
        }

        constexpr  T operator ()(const T& a, const T& b) const noexcept {
            return a > b ? a : b;
        }
    };


    // invを持つか調べる

    template<class, class = void>
    struct has_inv {
        static constexpr bool value = false;
    };

    template<class T>
    struct has_inv<T, std::void_t<decltype(&T::inv)>> {
        static constexpr bool value = true;
    };

    // invを持つか調べる

    template<class T>
    inline constexpr bool has_inv_v = has_inv<T>::value;
} // namespace kpr

#line 6 "kpr/data_structure/FenwickTree.hpp"

namespace kpr {
    // Binary Indexed Tree

    template<class T, class Op = Add<T>>
    struct FenwickTree {
        using value_type = T;
        using size_type = std::size_t;
        using reference = T&;
        using const_reference = const T&;
        using operator_type = Op;

    private:
        Op op;
        std::vector<T> tree;

    public:
        FenwickTree() noexcept = default;
        explicit FenwickTree(std::size_t n) noexcept: tree(n, op.id()) {}

        std::size_t size() const noexcept {
            return tree.size();
        }

        void apply(int p, const T& x) {
            ++p;
            while (p <= (int)tree.size()) {
                tree[p - 1] = op(tree[p - 1], x);
                p += p & -p;
            }
        }

        void set(int p, const T& x) {
            static_assert(has_inv_v<Op>, "Operator doesn't have an inverse");
            apply(p, op(x, op.inv(get(p))));
        }

        T get(int p) const {
            static_assert(has_inv_v<Op>, "Operator doesn't have an inverse");
            return op(prod(p + 1), op.inv(prod(p)));
        }

        T prod(int r) const {
            T s = op.id();
            while (r > 0) {
                s = op(s, tree[r - 1]);
                r -= r & -r;
            }
            return s;
        }
        T prod(int l, int r) const {
            static_assert(has_inv_v<Op>, "Operator doesn't have an inverse");
            return op(prod(r), op.inv(prod(l)));
        }

        T all_prod() const {
            return prod(tree.size());
        }
    };
} // namespace kpr

#line 2 "kpr/data_structure/SegmentTree.hpp"
#include <algorithm>
#line 6 "kpr/algorithm/bit.hpp"

namespace kpr {
    // 立っているbitの個数を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            static_assert(is_integer_v<T>, "The argument must be an integer");
            constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
            static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
            if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_popcount(x);
            else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_popcountl(x);
            else return __builtin_popcountll(x);
        }
    } pop_count;

    // 最上位bitより左の連続した0ビットの数を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            static_assert(is_integer_v<T>, "The argument must be an integer");
            constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
            static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
            if (x == 0) return 0;
            if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_clz(x) + digits - std::numeric_limits<unsigned int>::digits;
            else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_clzl(x) + digits - std::numeric_limits<unsigned long>::digits;
            else return __builtin_clzll(x) + digits - std::numeric_limits<unsigned long long>::digits;
        }
    } lzero_count;

    // 1の位から連続した0ビットの数を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            static_assert(is_integer_v<T>, "The argument must be an integer");
            constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
            if (x == 0) return digits;
            static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
            if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return __builtin_ctz(x);
            else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return __builtin_ctzl(x);
            else return __builtin_ctzll(x);
        }
    } rzero_count;

    // ビット幅を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            static_assert(is_integer_v<T>, "The argument must be an integer");
            constexpr auto digits = std::numeric_limits<std::make_unsigned_t<T>>::digits;
            static_assert(digits <= std::numeric_limits<unsigned long long>::digits, "The integer type of the argument is too large");
            if (x == 0) return 0;
            if constexpr (digits <= std::numeric_limits<unsigned int>::digits) return std::numeric_limits<unsigned int>::digits - __builtin_clz(x);
            else if constexpr (digits <= std::numeric_limits<unsigned long>::digits) return std::numeric_limits<unsigned long>::digits - __builtin_clzl(x);
            else return std::numeric_limits<unsigned long long>::digits - __builtin_clzll(x);
        }
    } bit_len;

    // 1 << n が与えられた数以下である最大の n を返す (0 の場合、0を返す)

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            return bit_len(x >> static_cast<T>(1));
        }
    } floor_bit;

    // 1 << n が与えられた数以上である最小の n を返す

    [[maybe_unused]] inline constexpr struct {
        template<class T>
        constexpr KYOPRO_BASE_INT operator ()(T x) const noexcept {
            if (x == 0) return 0;
            return bit_len(x - static_cast<T>(1));
        }
    } ceil_bit;
} // namespace kpr

#line 9 "kpr/data_structure/SegmentTree.hpp"

namespace kpr {
    template<class T, class Op = Add<T>>
    struct SegmentTree {
        using value_type = T;
        using num_type = std::size_t;
        using reference = T&;
        using const_reference = const T&;
        using operator_type = Op;

    private:
        int n, log, num;
        std::vector<T> tree;
        Op op;

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

    public:
        SegmentTree() noexcept = default;
        template<class... Args>
        explicit SegmentTree(Args&&... args) {
            std::vector<T> v(std::forward<Args>(args)...);
            n = v.size();
            log = ceil_bit(n);
            num = 1 << log;
            tree = std::vector<T>(num * 2, op.id());
            std::move(v.begin(), v.end(), tree.begin() + num);
            for (int i = num - 1; i >= 1; --i) update(i);
        }

        std::size_t size() const noexcept {
            return n;
        }

        void set(int p, const T& x) {
            p += num;
            tree[p] = x;
            for (int i = 1; i <= log; ++i) update(p >> i);
        }

        T get(int p) const {
            return tree[p + num];
        }

        T prod(int r) const {
            T sl = op.id(), sr = op.id();
            int l = num;
            r += num;
            while (l < r) {
                if (l & 1) {
                    sl = op(std::move(sl), tree[l]);
                    ++l;
                }
                if (r & 1) {
                    --r;
                    sr = op(tree[r], std::move(sr));
                }
                l >>= 1;
                r >>= 1;
            }
            return op(sl, sr);
        }
        T prod(int l, int r) const {
            T sl = op.id(), sr = op.id();
            l += num;
            r += num;
            while (l < r) {
                if (l & 1) {
                    sl = op(std::move(sl), tree[l]);
                    ++l;
                }
                if (r & 1) {
                    --r;
                    sr = op(tree[r], std::move(sr));
                }
                l >>= 1;
                r >>= 1;
            }
            return op(sl, sr);
        }

        T all_prod() const {
            return tree[1];
        }

        template<class F>
        KYOPRO_BASE_INT max_right(int l, F&& func) const {
            if (l == n) return n;
            l += num;
            T s = op.id();
            do {
                while (!(l & 1)) l >>= 1;
                if (!func(op(s, tree[l]))) {
                    while (l < num) {
                        l *= 2;
                        if (func(op(s, tree[l]))) {
                            s = op(std::move(s), tree[l]);
                            ++l;
                        }
                    }
                    return l - num;
                }
                s = op(std::move(s), tree[l]);
                ++l;
            } while ((l & -l) != l);
            return n;
        }

        template<class F>
        KYOPRO_BASE_INT min_left(int r, F&& func) const {
            if (r == 0) return 0;
            r += num;
            T s = op.id();
            do {
                --r;
                while (r > 1 && (r & 1)) r >>= 1;
                if (!func(op(tree[r], s))) {
                    while (r < num) {
                        r = r * 2 + 1;
                        if (func(op(tree[r], s))) {
                            s = op(tree[r], std::move(s));
                            --r;
                        }
                    }
                    return r + 1 - num;
                }
                s = op(tree[r], std::move(s));
            } while ((r & -r) != r);
            return 0;
        }
    };
} // namespace kpr
#line 4 "kpr/data_structure/UnionFind.hpp"
#include <unordered_map>
#line 9 "kpr/data_structure/UnionFind.hpp"

namespace kpr {
    struct UnionFind {
    private:
        std::vector<int> par;

    public:
        UnionFind() noexcept = default;
        UnionFind(std::size_t n) noexcept: par(n, -1) {}

        void resize(std::size_t n) {
            par.resize(n, -1);
        }
        void assign(std::size_t n) {
            par.assign(n, -1);
        }
        void clear() {
            std::fill(par.begin(), par.end(), -1);
        }

        std::size_t size() const noexcept {
            return par.size();
        }

        KYOPRO_BASE_INT find(int x) {
            int p = x;
            while (par[p] >= 0) p = par[p];
            while (x != p) {
                int tmp = x;
                x = par[x];
                par[tmp] = p;
            }
            return p;
        }

        bool merge(int x, int y) {
            x = find(x), y = find(y);
            if (x == y) return false;
            if (par[x] > par[y]) {
                par[y] += par[x];
                par[x] = y;
            } else {
                par[x] += par[y];
                par[y] = x;
            }
            return true;
        }

        bool same(int x, int y) {
            return find(x) == find(y);
        }

        KYOPRO_BASE_INT group_size(int x) {
            return -par[find(x)];
        }

        std::vector<int> group_members(int x) {
            x = find(x);
            std::vector<int> a;
            for (int i = 0; i < (int)(size()); ++i) if (find(i) == x) a.emplace_back(i);
            return a;
        }

        template<class Vector = std::vector<KYOPRO_BASE_INT>>
        Vector roots() const {
            Vector a;
            for (int i = 0; i < (int)(size()); ++i) if (par[i] < 0) a.emplace_back(i);
            return a;
        }

        KYOPRO_BASE_INT group_count() const {
            KYOPRO_BASE_INT cnt = 0;
            for (int i = 0; i < (int)(size()); ++i) if (par[i] < 0) ++cnt;
            return cnt;
        }

        template<class Map = std::unordered_map<KYOPRO_BASE_INT, std::vector<KYOPRO_BASE_INT>>>
        Map all_group_members() {
            Map group_members;
            for (int member = 0; member < (int)(size()); ++member) group_members[find(member)].emplace_back(member);
            return group_members;
        }
    };
} // namespace kpr

#line 10 "kpr/data_structure/WeightedUnionFind.hpp"

namespace kpr {
    template<class T, class Op = Add<T>>
    struct WeightedUnionFind {
    private:
        std::vector<int> par;
        std::vector<T> diff_weight;
        Op op;

    public:
        WeightedUnionFind() noexcept = default;
        WeightedUnionFind(std::size_t n) noexcept: par(n, -1), diff_weight(n, op.id()) {}

        void resize(std::size_t n) {
            par.resize(n, -1);
            diff_weight.resize(n, op.id());
        }
        void assign(std::size_t n) {
            par.assign(n, -1);
            diff_weight.assign(n, op.id());
        }
        void clear() {
            std::fill(par.begin(), par.end(), -1);
            std::fill(diff_weight.begin(), diff_weight.end(), op.id());
        }

        std::size_t size() const noexcept {
            return par.size();
        }

        KYOPRO_BASE_INT find(int x) {
            if (par[x] < 0) return x;
            int r = find(par[x]);
            diff_weight[x] = op(std::move(diff_weight[x]), diff_weight[par[x]]);
            return par[x] = r;
        }

        T weight(int x) {
            return find(x), diff_weight[x];
        }

        T diff(int x, int y) {
            return op(weight(y), op.inv(weight(x)));
        }

        bool merge(int x, int y, T w) {
            w = op(std::move(w), op(weight(x), op.inv(weight(y))));
            x = find(x), y = find(y);
            if (x == y) return false;
            if (par[x] > par[y]) {
                par[y] += par[x];
                par[x] = y;
                diff_weight[x] = op.inv(w);
            } else {
                par[x] += par[y];
                par[y] = x;
                diff_weight[y] = w;
            }
            return true;
        }

        bool same(int x, int y) {
            return find(x) == find(y);
        }

        KYOPRO_BASE_INT group_size(int x) {
            return -par[find(x)];
        }

        std::vector<int> group_members(int x) {
            x = find(x);
            std::vector<int> a;
            for (int i = 0; i < (int)(size()); ++i) if (find(i) == x) a.emplace_back(i);
            return a;
        }

        template<class Vector = std::vector<KYOPRO_BASE_INT>>
        Vector roots() const {
            Vector a;
            for (int i = 0; i < (int)(size()); ++i) if (par[i] < 0) a.emplace_back(i);
            return a;
        }

        KYOPRO_BASE_INT group_count() const {
            KYOPRO_BASE_INT cnt = 0;
            for (int i = 0; i < (int)(size()); ++i) if (par[i] < 0) ++cnt;
            return cnt;
        }

        template<class Map = std::unordered_map<KYOPRO_BASE_INT, std::vector<KYOPRO_BASE_INT>>>
        Map all_group_members() {
            Map group_members;
            for (int member = 0; member < (int)(size()); ++member) group_members[find(member)].emplace_back(member);
            return group_members;
        }
    };
} // namespace kpr
#line 6 "kpr/data_structure/data_structure.hpp"