CP-Algorithms Library

This documentation is automatically generated by competitive-verifier/competitive-verifier

View the Project on GitHub cp-algorithms/cp-algorithms-aux

:heavy_check_mark: cp-algo/structures/fenwick_set.hpp

Depends on

Verified with

Code

#ifndef CP_ALGO_STRUCTURES_FENWICK_SET_HPP
#define CP_ALGO_STRUCTURES_FENWICK_SET_HPP
#include "fenwick.hpp"
#include "bit_array.hpp"
namespace cp_algo::structures {
    template<size_t maxc>
    using popcount_array = std::array<int, maxc / bit_width<uint64_t> + 1>;
    // fenwick-based set for [0, maxc)
    template<size_t maxc>
    struct fenwick_set: fenwick<int, popcount_array<maxc>> {
        using Base = fenwick<int, popcount_array<maxc>>;
        static constexpr size_t word = bit_width<uint64_t>;
        size_t sz = 0;
        bit_array<maxc> bits;

        fenwick_set(): Base(popcount_array<maxc>{}) {}
        fenwick_set(auto &&range): fenwick_set() {
            for(auto x: range) {
                Base::data[x / word + 1] += 1;
                if(!bits.test(x)) {
                    sz++;
                    bits.flip(x);
                }
            }
            Base::to_prefix_folds();
        }
        void insert(size_t x) {
            if(bits.test(x)) return;
            Base::update(x / word, 1);
            bits.flip(x);
            sz++;
        }
        void erase(size_t x) {
            if(!bits.test(x)) return;
            Base::update(x / word, -1);
            bits.flip(x);
            sz--;
        }
        size_t order_of_key(size_t x) const {
            return Base::prefix_fold(x / word) + order_of_bit(bits.word(x / word), x % word);
        }
        size_t find_by_order(size_t order) const {
            if(order >= sz) {
                return -1;
            }
            auto [x, pref] = Base::prefix_lower_bound((int)order);
            return x * word + kth_set_bit(bits.word(x), order - pref);
        }
        size_t lower_bound(size_t x) const {
            if(bits.test(x)) {return x;}
            auto order = order_of_key(x);
            return order < sz ? find_by_order(order) : -1;
        }
        size_t pre_upper_bound(size_t x) const {
            if(bits.test(x)) {return x;}
            auto order = order_of_key(x);
            return order ? find_by_order(order - 1) : -1;
        }
    };
}
#endif // CP_ALGO_STRUCTURES_FENWICK_SET_HPP

#line 1 "cp-algo/structures/fenwick_set.hpp"


#line 1 "cp-algo/structures/fenwick.hpp"


#line 1 "cp-algo/util/big_alloc.hpp"



#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstddef>
#include <bit>
#include <iostream>
#include <forward_list>

// Single macro to detect POSIX platforms (Linux, Unix, macOS)
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#define CP_ALGO_USE_MMAP 1
#include <sys/mman.h>
#else
#define CP_ALGO_USE_MMAP 0
#endif

namespace cp_algo {
    template<typename T, size_t Align = 32>
    class big_alloc {
        static_assert(Align >= alignof(void*), "Align must be at least pointer-size");
        static_assert(std::has_single_bit(Align), "Align must be a power of two");

    public:
        using value_type = T;
        template<class U>
        struct rebind {
            using other = big_alloc<U, Align>;
        };
        constexpr bool operator==(const big_alloc&) const = default;

        big_alloc() noexcept = default;
        template<typename U, std::size_t A>
        big_alloc(const big_alloc<U, A>&) noexcept {}

        [[nodiscard]] T* allocate(std::size_t n) {
            std::size_t padded = round_up(n * sizeof(T));
            std::size_t align = std::max<std::size_t>(alignof(T), Align);
#if CP_ALGO_USE_MMAP
            if(padded >= MEGABYTE) {
                void* raw = mmap(nullptr, padded, PROT_READ | PROT_WRITE, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
                madvise(raw, padded, MADV_HUGEPAGE);
                return static_cast<T*>(raw);
            }
#endif
            return static_cast<T*>(::operator new(padded, std::align_val_t(align)));
        }

        void deallocate(T* p, std::size_t n) noexcept {
            if(!p) {
                return;
            }
            std::size_t padded = round_up(n * sizeof(T));
            std::size_t align = std::max<std::size_t>(alignof(T), Align);
#if CP_ALGO_USE_MMAP
            if(padded >= MEGABYTE) {
                munmap(p, padded);
                return;
            }
#endif
            ::operator delete(p, padded, std::align_val_t(align));
        }

    private:
        static constexpr std::size_t MEGABYTE = 1 << 20;
        static constexpr std::size_t round_up(std::size_t x) noexcept {
            return (x + Align - 1) / Align * Align;
        }
    };

    template<typename T>
    using big_vector = std::vector<T, big_alloc<T>>;
    template<typename T>
    using big_basic_string = std::basic_string<T, std::char_traits<T>, big_alloc<T>>;
    template<typename T>
    using big_deque = std::deque<T, big_alloc<T>>;
    template<typename T>
    using big_stack = std::stack<T, big_deque<T>>;
    template<typename T>
    using big_queue = std::queue<T, big_deque<T>>;
    template<typename T>
    using big_priority_queue = std::priority_queue<T, big_vector<T>>;
    template<typename T>
    using big_forward_list = std::forward_list<T, big_alloc<T>>;
    using big_string = big_basic_string<char>;

    template<typename Key, typename Value, typename Compare = std::less<Key>>
    using big_map = std::map<Key, Value, Compare, big_alloc<std::pair<const Key, Value>>>;
    template<typename T, typename Compare = std::less<T>>
    using big_multiset = std::multiset<T, Compare, big_alloc<T>>;
    template<typename T, typename Compare = std::less<T>>
    using big_set = std::set<T, Compare, big_alloc<T>>;
}


#line 4 "cp-algo/structures/fenwick.hpp"
#include <cassert>
#line 6 "cp-algo/structures/fenwick.hpp"
namespace cp_algo::structures {
    template <typename Op>
    struct inverse_op {};

    template <typename T>
    struct inverse_op<std::plus<T>> {
        static T apply(T const& a, T const& b) {
            return a - b;
        }
    };

    template <typename T>
    struct inverse_op<std::multiplies<T>> {
        static T apply(T const& a, T const& b) {
            return a / b;
        }
    };

    template<typename T, std::ranges::range Container = big_vector<T>, typename Op = std::plus<T>>
    struct fenwick {
        Op op;
        size_t n;
        Container data;

        fenwick(auto &&range, Op &&op = Op{}): op(std::move(op)) {
            assign(std::move(range));
        }
        void to_prefix_folds() {
            for(size_t i = 1; i < n; i++) {
                if(i + (i & -i) <= n) {
                    data[i + (i & -i)] = op(data[i + (i & -i)], data[i]);
                }
            }
        }
        void assign(auto &&range) {
            n = size(range) - 1;
            data = std::move(range);
            to_prefix_folds();
        }
        void update(size_t x, T const& v) {
            for(++x; x <= n; x += x & -x) {
                data[x] = op(data[x], v);
            }
        }
        // fold of [0, r)
        T prefix_fold(size_t r) const {
            assert(r <= n);
            T res = {};
            for(; r; r -= r & -r) {
                res = op(res, data[r]);
            }
            return res;
        }
        // fold of [l, r)
        T range_fold(size_t l, size_t r) const {
            return inverse_op<Op>::apply(prefix_fold(r), prefix_fold(l));
        }
        // Last x s.t. prefix_fold(x) <= k
        // Assumes prefix_fold is monotonic
        // returns [x, prefix_fold(x)]
        auto prefix_lower_bound(T k) const {
            size_t x = 0;
            T pref = {};
            for(size_t i = std::bit_floor(n); i; i /= 2) {
                if(x + i <= n && op(pref, data[x + i]) <= k) {
                    pref = op(pref, data[x + i]);
                    x += i;
                }
            }
            return std::pair{x, pref};
        }
    };

    template<std::ranges::range Container, typename Op>
    fenwick(Container&&, Op&&) -> fenwick<std::ranges::range_value_t<Container>, Container, Op>;
    template<std::ranges::range Container>
    fenwick(Container&&) -> fenwick<std::ranges::range_value_t<Container>, Container>;

    auto maxer = [](auto const& a, auto const& b) {
        return std::max(a, b);
    };
    template<typename T, std::ranges::range Container = big_vector<T>>
    struct fenwick_max: fenwick<T, Container, decltype(maxer)> {
        using fenwick<T, Container, decltype(maxer)>::fenwick;
    };
    template<std::ranges::range Container>
    fenwick_max(Container&&) -> fenwick_max<std::ranges::range_value_t<Container>, Container>;

}

#line 1 "cp-algo/structures/bit_array.hpp"


#line 1 "cp-algo/util/bit.hpp"


#line 1 "cp-algo/util/simd.hpp"


#include <experimental/simd>
#include <cstdint>
#line 6 "cp-algo/util/simd.hpp"
#include <memory>

#if defined(__x86_64__) && !defined(CP_ALGO_DISABLE_AVX2)
#define CP_ALGO_SIMD_AVX2_TARGET _Pragma("GCC target(\"avx2,fma\")")
#else
#define CP_ALGO_SIMD_AVX2_TARGET
#endif

#define CP_ALGO_SIMD_PRAGMA_PUSH \
    _Pragma("GCC push_options") \
    CP_ALGO_SIMD_AVX2_TARGET

CP_ALGO_SIMD_PRAGMA_PUSH
namespace cp_algo {
    template<typename T, size_t len>
    using simd [[gnu::vector_size(len * sizeof(T))]] = T;
    using u64x8 = simd<uint64_t, 8>;
    using u32x16 = simd<uint32_t, 16>;
    using i64x4 = simd<int64_t, 4>;
    using u64x4 = simd<uint64_t, 4>;
    using u32x8 = simd<uint32_t, 8>;
    using u16x16 = simd<uint16_t, 16>;
    using i32x4 = simd<int32_t, 4>;
    using u32x4 = simd<uint32_t, 4>;
    using u16x8 = simd<uint16_t, 8>;
    using u16x4 = simd<uint16_t, 4>;
    using i16x4 = simd<int16_t, 4>;
    using u8x32 = simd<uint8_t, 32>;
    using u8x16 = simd<uint8_t, 16>;
    using u8x8 = simd<uint8_t, 8>;
    using u8x4 = simd<uint8_t, 4>;
    using dx4 = simd<double, 4>;

    inline dx4 abs(dx4 a) {
        return dx4{
            std::abs(a[0]),
            std::abs(a[1]),
            std::abs(a[2]),
            std::abs(a[3])
        };
    }

    // https://stackoverflow.com/a/77376595
    // works for ints in (-2^51, 2^51)
    static constexpr dx4 magic = dx4() + (3ULL << 51);
    inline i64x4 lround(dx4 x) {
        return i64x4(x + magic) - i64x4(magic);
    }
    inline dx4 to_double(i64x4 x) {
        return dx4(x + i64x4(magic)) - magic;
    }

    inline dx4 round(dx4 a) {
        return dx4{
            std::nearbyint(a[0]),
            std::nearbyint(a[1]),
            std::nearbyint(a[2]),
            std::nearbyint(a[3])
        };
    }

    inline u64x4 low32(u64x4 x) {
        return x & uint32_t(-1);
    }
    inline auto swap_bytes(auto x) {
        return decltype(x)(__builtin_shufflevector(u32x8(x), u32x8(x), 1, 0, 3, 2, 5, 4, 7, 6));
    }
    inline u64x4 montgomery_reduce(u64x4 x, uint32_t mod, uint32_t imod) {
#ifdef __AVX2__
        auto x_ninv = u64x4(_mm256_mul_epu32(__m256i(x), __m256i() + imod));
        x += u64x4(_mm256_mul_epu32(__m256i(x_ninv), __m256i() + mod));
#else
        auto x_ninv = u64x4(u32x8(low32(x)) * imod);
        x += x_ninv * uint64_t(mod);
#endif
        return swap_bytes(x);
    }

    // x - mod where x >= mod, for x in [0, 2 mod). Unsigned, so it holds up to mod < 2^31;
    // zero upper halves of 64-bit lanes stay zero.
    inline u32x8 reduce_once(u32x8 x, uint32_t mod) {
        auto y = x - mod;
        return x < y ? x : y;
    }
    inline u64x4 reduce_once(u64x4 x, uint32_t mod) {
        return u64x4(reduce_once(u32x8(x), mod));
    }

    inline u64x4 montgomery_mul(u64x4 x, u64x4 y, uint32_t mod, uint32_t imod) {
#ifdef __AVX2__
        return montgomery_reduce(u64x4(_mm256_mul_epu32(__m256i(x), __m256i(y))), mod, imod);
#else
        return montgomery_reduce(x * y, mod, imod);
#endif
    }
    inline u32x8 montgomery_mul(u32x8 x, u32x8 y, uint32_t mod, uint32_t imod) {
        return u32x8(montgomery_mul(u64x4(x), u64x4(y), mod, imod)) |
               u32x8(swap_bytes(montgomery_mul(u64x4(swap_bytes(x)), u64x4(swap_bytes(y)), mod, imod)));
    }
    inline dx4 rotate_right(dx4 x) {
        static constexpr u64x4 shuffler = {3, 0, 1, 2};
        return __builtin_shuffle(x, shuffler);
    }

    template<std::size_t Align = 32>
    inline bool is_aligned(const auto *p) noexcept {
        return (reinterpret_cast<std::uintptr_t>(p) % Align) == 0;
    }

    template<class Target>
    inline Target& vector_cast(auto &&p) {
        return *reinterpret_cast<Target*>(std::assume_aligned<alignof(Target)>(&p));
    }
}
#pragma GCC pop_options

#line 6 "cp-algo/util/bit.hpp"
#include <array>
#line 8 "cp-algo/util/bit.hpp"

#if defined(__x86_64__) && !defined(CP_ALGO_DISABLE_AVX2)
#define CP_ALGO_BIT_OPS_TARGET _Pragma("GCC target(\"avx2,bmi,bmi2,lzcnt,popcnt\")")
#else
#define CP_ALGO_BIT_OPS_TARGET _Pragma("GCC target(\"bmi,bmi2,lzcnt,popcnt\")")
#endif

#define CP_ALGO_BIT_PRAGMA_PUSH \
    _Pragma("GCC push_options") \
    CP_ALGO_BIT_OPS_TARGET

CP_ALGO_BIT_PRAGMA_PUSH
namespace cp_algo {
    template<typename Uint>
    constexpr size_t bit_width = sizeof(Uint) * 8;

    // n < 64
    uint64_t mask(size_t n) {
        return (1ULL << n) - 1;
    }
    size_t order_of_bit(auto x, size_t k) {
        return k ? std::popcount(x << (bit_width<decltype(x)> - k)) : 0;
    }
    inline size_t kth_set_bit(uint64_t x, size_t k) {
        return std::countr_zero(_pdep_u64(1ULL << k, x));
    }
    template<int fl = 0>
    void with_bit_floor(size_t n, auto &&callback) {
        if constexpr (fl >= 63) {
            return;
        } else if (n >> (fl + 1)) {
            with_bit_floor<fl + 1>(n, callback);
        } else {
            callback.template operator()<1ULL << fl>();
        }
    }
    void with_bit_ceil(size_t n, auto &&callback) {
        with_bit_floor(n, [&]<size_t N>() {
            if(N == n) {
                callback.template operator()<N>();
            } else {
                callback.template operator()<N << 1>();
            }
        });
    }

    inline uint32_t read_bits(char const* p) {
        return _mm256_movemask_epi8(__m256i(vector_cast<u8x32 const>(p[0]) + (127 - '0')));
    }
    inline uint64_t read_bits64(char const* p) {
        return read_bits(p) | (uint64_t(read_bits(p + 32)) << 32);
    }

    inline void write_bits(char *p, uint32_t bits) {
        static constexpr u8x32 shuffler = {
            0, 0, 0, 0, 0, 0, 0, 0,
            1, 1, 1, 1, 1, 1, 1, 1,
            2, 2, 2, 2, 2, 2, 2, 2,
            3, 3, 3, 3, 3, 3, 3, 3
        };
        auto shuffled = u8x32(_mm256_shuffle_epi8(__m256i() + bits, __m256i(shuffler)));
        static constexpr u8x32 mask = {
            1, 2, 4, 8, 16, 32, 64, 128,
            1, 2, 4, 8, 16, 32, 64, 128,
            1, 2, 4, 8, 16, 32, 64, 128,
            1, 2, 4, 8, 16, 32, 64, 128
        };
        for(int z = 0; z < 32; z++) {
            p[z] = shuffled[z] & mask[z] ? '1' : '0';
        }
    }
    inline void write_bits64(char *p, uint64_t bits) {
        write_bits(p, uint32_t(bits));
        write_bits(p + 32, uint32_t(bits >> 32));
    }
}
#pragma GCC pop_options

#line 6 "cp-algo/structures/bit_array.hpp"
CP_ALGO_SIMD_PRAGMA_PUSH
namespace cp_algo::structures {
    template<typename C>
    concept Resizable = requires(C& c, std::size_t n) { c.resize(n); };

    template<class Cont>
    struct _bit_array {
        using word_t = typename Cont::value_type;
        static constexpr size_t width = bit_width<word_t>;
        size_t words, n;
        alignas(32) Cont data;

        constexpr void resize(size_t N) {
            n = N;
            words = (n + width - 1) / width;
            if constexpr (Resizable<Cont>) {
                data.resize(words);
            } else {
                assert(std::size(data) >= words);
            }
        }

        constexpr _bit_array(): data() {
            if constexpr (!Resizable<Cont>) {
                resize(std::size(data) * width);
            } else {
                resize(0);
            }
        }
        constexpr _bit_array(size_t N): data() {
            resize(N);
        }
        constexpr auto&& word(this auto&& self, size_t x) {
            return self.data[x];
        }
        constexpr void set_all(word_t val = -1) {
            for(size_t i = 0; i < words; i++) {
                data[i] = val;
            }
        }
        constexpr void reset() {
            set_all(0);
        }
        constexpr void set(size_t x) {
            word(x / width) |= 1ULL << (x % width);
        }
        constexpr void reset(size_t x) {
            word(x / width) &= ~(1ULL << (x % width));
        }
        constexpr void flip(size_t x) {
            word(x / width) ^= 1ULL << (x % width);
        }
        constexpr bool test(size_t x) const {
            return (word(x / width) >> (x % width)) & 1;
        }
        constexpr bool operator[](size_t x) const {
            return test(x);
        }
        constexpr size_t size() const {
            return n;
        }
        
        auto operator <=> (_bit_array const& t) const = default;
        
        constexpr _bit_array& xor_hint(_bit_array const& t, size_t hint) {
            for(size_t i = hint / width; i < words; i++) {
                data[i] ^= t.data[i];
            }
            return *this;
        }
        constexpr _bit_array& operator ^= (_bit_array const& t) {
            return xor_hint(t, 0);
        }
        constexpr _bit_array operator ^ (_bit_array const& t) const {
            return _bit_array(*this) ^= t;
        }
    };

    template<size_t N>
    using bit_array = _bit_array<std::array<uint64_t, (N + 63) / 64>>;
    using dynamic_bit_array = _bit_array<big_vector<uint64_t>>;
}
#pragma GCC pop_options

#line 5 "cp-algo/structures/fenwick_set.hpp"
namespace cp_algo::structures {
    template<size_t maxc>
    using popcount_array = std::array<int, maxc / bit_width<uint64_t> + 1>;
    // fenwick-based set for [0, maxc)
    template<size_t maxc>
    struct fenwick_set: fenwick<int, popcount_array<maxc>> {
        using Base = fenwick<int, popcount_array<maxc>>;
        static constexpr size_t word = bit_width<uint64_t>;
        size_t sz = 0;
        bit_array<maxc> bits;

        fenwick_set(): Base(popcount_array<maxc>{}) {}
        fenwick_set(auto &&range): fenwick_set() {
            for(auto x: range) {
                Base::data[x / word + 1] += 1;
                if(!bits.test(x)) {
                    sz++;
                    bits.flip(x);
                }
            }
            Base::to_prefix_folds();
        }
        void insert(size_t x) {
            if(bits.test(x)) return;
            Base::update(x / word, 1);
            bits.flip(x);
            sz++;
        }
        void erase(size_t x) {
            if(!bits.test(x)) return;
            Base::update(x / word, -1);
            bits.flip(x);
            sz--;
        }
        size_t order_of_key(size_t x) const {
            return Base::prefix_fold(x / word) + order_of_bit(bits.word(x / word), x % word);
        }
        size_t find_by_order(size_t order) const {
            if(order >= sz) {
                return -1;
            }
            auto [x, pref] = Base::prefix_lower_bound((int)order);
            return x * word + kth_set_bit(bits.word(x), order - pref);
        }
        size_t lower_bound(size_t x) const {
            if(bits.test(x)) {return x;}
            auto order = order_of_key(x);
            return order < sz ? find_by_order(order) : -1;
        }
        size_t pre_upper_bound(size_t x) const {
            if(bits.test(x)) {return x;}
            auto order = order_of_key(x);
            return order ? find_by_order(order - 1) : -1;
        }
    };
}


#ifndef CP_ALGO_STRUCTURES_FENWICK_SET_HPP
#define CP_ALGO_STRUCTURES_FENWICK_SET_HPP
#include "fenwick.hpp"
#include "bit_array.hpp"
namespace cp_algo::structures{ template<size_t maxc> using popcount_array=std::array<int,maxc/bit_width<uint64_t> +1>; template<size_t maxc> struct fenwick_set:fenwick<int,popcount_array<maxc>>{ using Base=fenwick<int,popcount_array<maxc>>; static constexpr size_t word=bit_width<uint64_t>; size_t sz=0; bit_array<maxc>bits; fenwick_set():Base(popcount_array<maxc>{}){} fenwick_set(auto&&range):fenwick_set(){ for(auto x:range){ Base::data[x/word+1] +=1; if(!bits.test(x)){ sz++; bits.flip(x); } } Base::to_prefix_folds(); } void insert(size_t x){ if(bits.test(x))return; Base::update(x/word,1); bits.flip(x); sz++; } void erase(size_t x){ if(!bits.test(x))return; Base::update(x/word,-1); bits.flip(x); sz--; } size_t order_of_key(size_t x)const{ return Base::prefix_fold(x/word)+order_of_bit(bits.word(x/word),x%word); } size_t find_by_order(size_t order)const{ if(order>=sz){ return-1; } auto[x,pref] =Base::prefix_lower_bound((int)order); return x*word+kth_set_bit(bits.word(x),order-pref); } size_t lower_bound(size_t x)const{ if(bits.test(x)){return x;} auto order=order_of_key(x); return order<sz?find_by_order(order): -1; } size_t pre_upper_bound(size_t x)const{ if(bits.test(x)){return x;} auto order=order_of_key(x); return order?find_by_order(order-1): -1; } }; }
#endif

#line 1 "cp-algo/structures/fenwick_set.hpp"
#line 1 "cp-algo/structures/fenwick.hpp"
#line 1 "cp-algo/util/big_alloc.hpp"
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <cstddef>
#include <bit>
#include <iostream>
#include <forward_list>
#if defined(__linux__) || defined(__unix__) || (defined(__APPLE__) && defined(__MACH__))
#define CP_ALGO_USE_MMAP 1
#include <sys/mman.h>
#else
#define CP_ALGO_USE_MMAP 0
#endif
namespace cp_algo{ template<typename T,size_t Align=32> class big_alloc{ static_assert(Align>=alignof(void*),"Align must be at least pointer-size"); static_assert(std::has_single_bit(Align),"Align must be a power of two"); public: using value_type=T; template<class U> struct rebind{ using other=big_alloc<U,Align>; }; constexpr bool operator==(const big_alloc&)const=default; big_alloc()noexcept=default; template<typename U,std::size_t A> big_alloc(const big_alloc<U,A>&)noexcept{} [[nodiscard]]T*allocate(std::size_t n){ std::size_t padded=round_up(n*sizeof(T)); std::size_t align=std::max<std::size_t>(alignof(T),Align);
#if CP_ALGO_USE_MMAP
if(padded>=MEGABYTE){ void*raw=mmap(nullptr,padded,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANONYMOUS,-1,0); madvise(raw,padded,MADV_HUGEPAGE); return static_cast<T*>(raw); }
#endif
return static_cast<T*>(::operator new(padded,std::align_val_t(align))); } void deallocate(T*p,std::size_t n)noexcept{ if(!p){ return; } std::size_t padded=round_up(n*sizeof(T)); std::size_t align=std::max<std::size_t>(alignof(T),Align);
#if CP_ALGO_USE_MMAP
if(padded>=MEGABYTE){ munmap(p,padded); return; }
#endif
::operator delete(p,padded,std::align_val_t(align)); } private: static constexpr std::size_t MEGABYTE=1<<20; static constexpr std::size_t round_up(std::size_t x)noexcept{ return(x+Align-1)/Align*Align; } }; template<typename T> using big_vector=std::vector<T,big_alloc<T>>; template<typename T> using big_basic_string=std::basic_string<T,std::char_traits<T>,big_alloc<T>>; template<typename T> using big_deque=std::deque<T,big_alloc<T>>; template<typename T> using big_stack=std::stack<T,big_deque<T>>; template<typename T> using big_queue=std::queue<T,big_deque<T>>; template<typename T> using big_priority_queue=std::priority_queue<T,big_vector<T>>; template<typename T> using big_forward_list=std::forward_list<T,big_alloc<T>>; using big_string=big_basic_string<char>; template<typename Key,typename Value,typename Compare=std::less<Key>> using big_map=std::map<Key,Value,Compare,big_alloc<std::pair<const Key,Value>>>; template<typename T,typename Compare=std::less<T>> using big_multiset=std::multiset<T,Compare,big_alloc<T>>; template<typename T,typename Compare=std::less<T>> using big_set=std::set<T,Compare,big_alloc<T>>; }
#line 4 "cp-algo/structures/fenwick.hpp"
#include <cassert>
#line 6 "cp-algo/structures/fenwick.hpp"
namespace cp_algo::structures{ template<typename Op> struct inverse_op{}; template<typename T> struct inverse_op<std::plus<T>>{ static T apply(T const&a,T const&b){ return a-b; } }; template<typename T> struct inverse_op<std::multiplies<T>>{ static T apply(T const&a,T const&b){ return a/b; } }; template<typename T,std::ranges::range Container=big_vector<T>,typename Op=std::plus<T>> struct fenwick{ Op op; size_t n; Container data; fenwick(auto&&range,Op&&op=Op{}):op(std::move(op)){ assign(std::move(range)); } void to_prefix_folds(){ for(size_t i=1;i<n;i++){ if(i+(i& -i)<=n){ data[i+(i& -i)] =op(data[i+(i& -i)],data[i]); } } } void assign(auto&&range){ n=size(range)-1; data=std::move(range); to_prefix_folds(); } void update(size_t x,T const&v){ for(++x;x<=n;x+=x& -x){ data[x] =op(data[x],v); } } T prefix_fold(size_t r)const{ assert(r<=n); T res={}; for(;r;r-=r& -r){ res=op(res,data[r]); } return res; } T range_fold(size_t l,size_t r)const{ return inverse_op<Op>::apply(prefix_fold(r),prefix_fold(l)); } auto prefix_lower_bound(T k)const{ size_t x=0; T pref={}; for(size_t i=std::bit_floor(n);i;i/=2){ if(x+i<=n&&op(pref,data[x+i])<=k){ pref=op(pref,data[x+i]); x+=i; } } return std::pair{x,pref}; } }; template<std::ranges::range Container,typename Op> fenwick(Container&&,Op&&)->fenwick<std::ranges::range_value_t<Container>,Container,Op>; template<std::ranges::range Container> fenwick(Container&&)->fenwick<std::ranges::range_value_t<Container>,Container>; auto maxer= [](auto const&a,auto const&b){ return std::max(a,b); }; template<typename T,std::ranges::range Container=big_vector<T>> struct fenwick_max:fenwick<T,Container,decltype(maxer)>{ using fenwick<T,Container,decltype(maxer)>::fenwick; }; template<std::ranges::range Container> fenwick_max(Container&&)->fenwick_max<std::ranges::range_value_t<Container>,Container>; }
#line 1 "cp-algo/structures/bit_array.hpp"
#line 1 "cp-algo/util/bit.hpp"
#line 1 "cp-algo/util/simd.hpp"
#include <experimental/simd>
#include <cstdint>
#line 6 "cp-algo/util/simd.hpp"
#include <memory>
#if defined(__x86_64__) && !defined(CP_ALGO_DISABLE_AVX2)
#define CP_ALGO_SIMD_AVX2_TARGET _Pragma("GCC target(\"avx2,fma\")")
#else
#define CP_ALGO_SIMD_AVX2_TARGET
#endif
#define CP_ALGO_SIMD_PRAGMA_PUSH  _Pragma("GCC push_options")  CP_ALGO_SIMD_AVX2_TARGET
CP_ALGO_SIMD_PRAGMA_PUSH
namespace cp_algo{ template<typename T,size_t len> using simd[[gnu::vector_size(len*sizeof(T))]] =T; using u64x8=simd<uint64_t,8>; using u32x16=simd<uint32_t,16>; using i64x4=simd<int64_t,4>; using u64x4=simd<uint64_t,4>; using u32x8=simd<uint32_t,8>; using u16x16=simd<uint16_t,16>; using i32x4=simd<int32_t,4>; using u32x4=simd<uint32_t,4>; using u16x8=simd<uint16_t,8>; using u16x4=simd<uint16_t,4>; using i16x4=simd<int16_t,4>; using u8x32=simd<uint8_t,32>; using u8x16=simd<uint8_t,16>; using u8x8=simd<uint8_t,8>; using u8x4=simd<uint8_t,4>; using dx4=simd<double,4>; inline dx4 abs(dx4 a){ return dx4{ std::abs(a[0]), std::abs(a[1]), std::abs(a[2]), std::abs(a[3]) }; } static constexpr dx4 magic=dx4()+(3ULL<<51); inline i64x4 lround(dx4 x){ return i64x4(x+magic)-i64x4(magic); } inline dx4 to_double(i64x4 x){ return dx4(x+i64x4(magic))-magic; } inline dx4 round(dx4 a){ return dx4{ std::nearbyint(a[0]), std::nearbyint(a[1]), std::nearbyint(a[2]), std::nearbyint(a[3]) }; } inline u64x4 low32(u64x4 x){ return x&uint32_t(-1); } inline auto swap_bytes(auto x){ return decltype(x)(__builtin_shufflevector(u32x8(x),u32x8(x),1,0,3,2,5,4,7,6)); } inline u64x4 montgomery_reduce(u64x4 x,uint32_t mod,uint32_t imod){
#ifdef __AVX2__
auto x_ninv=u64x4(_mm256_mul_epu32(__m256i(x),__m256i()+imod)); x+=u64x4(_mm256_mul_epu32(__m256i(x_ninv),__m256i()+mod));
#else
auto x_ninv=u64x4(u32x8(low32(x))*imod); x+=x_ninv*uint64_t(mod);
#endif
return swap_bytes(x); } inline u32x8 reduce_once(u32x8 x,uint32_t mod){ auto y=x-mod; return x<y?x:y; } inline u64x4 reduce_once(u64x4 x,uint32_t mod){ return u64x4(reduce_once(u32x8(x),mod)); } inline u64x4 montgomery_mul(u64x4 x,u64x4 y,uint32_t mod,uint32_t imod){
#ifdef __AVX2__
return montgomery_reduce(u64x4(_mm256_mul_epu32(__m256i(x),__m256i(y))),mod,imod);
#else
return montgomery_reduce(x*y,mod,imod);
#endif
} inline u32x8 montgomery_mul(u32x8 x,u32x8 y,uint32_t mod,uint32_t imod){ return u32x8(montgomery_mul(u64x4(x),u64x4(y),mod,imod))| u32x8(swap_bytes(montgomery_mul(u64x4(swap_bytes(x)),u64x4(swap_bytes(y)),mod,imod))); } inline dx4 rotate_right(dx4 x){ static constexpr u64x4 shuffler={3,0,1,2}; return __builtin_shuffle(x,shuffler); } template<std::size_t Align=32> inline bool is_aligned(const auto*p)noexcept{ return(reinterpret_cast<std::uintptr_t>(p)%Align)==0; } template<class Target> inline Target&vector_cast(auto&&p){ return*reinterpret_cast<Target*>(std::assume_aligned<alignof(Target)>(&p)); } }
#pragma GCC pop_options
#line 6 "cp-algo/util/bit.hpp"
#include <array>
#line 8 "cp-algo/util/bit.hpp"
#if defined(__x86_64__) && !defined(CP_ALGO_DISABLE_AVX2)
#define CP_ALGO_BIT_OPS_TARGET _Pragma("GCC target(\"avx2,bmi,bmi2,lzcnt,popcnt\")")
#else
#define CP_ALGO_BIT_OPS_TARGET _Pragma("GCC target(\"bmi,bmi2,lzcnt,popcnt\")")
#endif
#define CP_ALGO_BIT_PRAGMA_PUSH  _Pragma("GCC push_options")  CP_ALGO_BIT_OPS_TARGET
CP_ALGO_BIT_PRAGMA_PUSH
namespace cp_algo{ template<typename Uint> constexpr size_t bit_width=sizeof(Uint)*8; uint64_t mask(size_t n){ return(1ULL<<n)-1; } size_t order_of_bit(auto x,size_t k){ return k?std::popcount(x<<(bit_width<decltype(x)> -k)):0; } inline size_t kth_set_bit(uint64_t x,size_t k){ return std::countr_zero(_pdep_u64(1ULL<<k,x)); } template<int fl=0> void with_bit_floor(size_t n,auto&&callback){ if constexpr(fl>=63){ return; }else if(n>>(fl+1)){ with_bit_floor<fl+1>(n,callback); }else{ callback.template operator()<1ULL<<fl>(); } } void with_bit_ceil(size_t n,auto&&callback){ with_bit_floor(n,[&]<size_t N>(){ if(N==n){ callback.template operator()<N>(); }else{ callback.template operator()<N<<1>(); } }); } inline uint32_t read_bits(char const*p){ return _mm256_movemask_epi8(__m256i(vector_cast<u8x32 const>(p[0])+(127-'0'))); } inline uint64_t read_bits64(char const*p){ return read_bits(p)|(uint64_t(read_bits(p+32))<<32); } inline void write_bits(char*p,uint32_t bits){ static constexpr u8x32 shuffler={ 0,0,0,0,0,0,0,0, 1,1,1,1,1,1,1,1, 2,2,2,2,2,2,2,2, 3,3,3,3,3,3,3,3 }; auto shuffled=u8x32(_mm256_shuffle_epi8(__m256i()+bits,__m256i(shuffler))); static constexpr u8x32 mask={ 1,2,4,8,16,32,64,128, 1,2,4,8,16,32,64,128, 1,2,4,8,16,32,64,128, 1,2,4,8,16,32,64,128 }; for(int z=0;z<32;z++){ p[z] =shuffled[z] &mask[z]?'1':'0'; } } inline void write_bits64(char*p,uint64_t bits){ write_bits(p,uint32_t(bits)); write_bits(p+32,uint32_t(bits>>32)); } }
#pragma GCC pop_options
#line 6 "cp-algo/structures/bit_array.hpp"
CP_ALGO_SIMD_PRAGMA_PUSH
namespace cp_algo::structures{ template<typename C> concept Resizable=requires(C&c,std::size_t n){c.resize(n);}; template<class Cont> struct _bit_array{ using word_t=typename Cont::value_type; static constexpr size_t width=bit_width<word_t>; size_t words,n; alignas(32)Cont data; constexpr void resize(size_t N){ n=N; words=(n+width-1)/width; if constexpr(Resizable<Cont>){ data.resize(words); }else{ assert(std::size(data)>=words); } } constexpr _bit_array():data(){ if constexpr(!Resizable<Cont>){ resize(std::size(data)*width); }else{ resize(0); } } constexpr _bit_array(size_t N):data(){ resize(N); } constexpr auto&&word(this auto&&self,size_t x){ return self.data[x]; } constexpr void set_all(word_t val= -1){ for(size_t i=0;i<words;i++){ data[i] =val; } } constexpr void reset(){ set_all(0); } constexpr void set(size_t x){ word(x/width)|=1ULL<<(x%width); } constexpr void reset(size_t x){ word(x/width)&= ~(1ULL<<(x%width)); } constexpr void flip(size_t x){ word(x/width)^=1ULL<<(x%width); } constexpr bool test(size_t x)const{ return(word(x/width)>>(x%width))&1; } constexpr bool operator[](size_t x)const{ return test(x); } constexpr size_t size()const{ return n; } auto operator<=>(_bit_array const&t)const=default; constexpr _bit_array&xor_hint(_bit_array const&t,size_t hint){ for(size_t i=hint/width;i<words;i++){ data[i] ^=t.data[i]; } return*this; } constexpr _bit_array&operator^=(_bit_array const&t){ return xor_hint(t,0); } constexpr _bit_array operator^(_bit_array const&t)const{ return _bit_array(*this)^=t; } }; template<size_t N> using bit_array=_bit_array<std::array<uint64_t,(N+63)/64>>; using dynamic_bit_array=_bit_array<big_vector<uint64_t>>; }
#pragma GCC pop_options
#line 5 "cp-algo/structures/fenwick_set.hpp"
namespace cp_algo::structures{ template<size_t maxc> using popcount_array=std::array<int,maxc/bit_width<uint64_t> +1>; template<size_t maxc> struct fenwick_set:fenwick<int,popcount_array<maxc>>{ using Base=fenwick<int,popcount_array<maxc>>; static constexpr size_t word=bit_width<uint64_t>; size_t sz=0; bit_array<maxc>bits; fenwick_set():Base(popcount_array<maxc>{}){} fenwick_set(auto&&range):fenwick_set(){ for(auto x:range){ Base::data[x/word+1] +=1; if(!bits.test(x)){ sz++; bits.flip(x); } } Base::to_prefix_folds(); } void insert(size_t x){ if(bits.test(x))return; Base::update(x/word,1); bits.flip(x); sz++; } void erase(size_t x){ if(!bits.test(x))return; Base::update(x/word,-1); bits.flip(x); sz--; } size_t order_of_key(size_t x)const{ return Base::prefix_fold(x/word)+order_of_bit(bits.word(x/word),x%word); } size_t find_by_order(size_t order)const{ if(order>=sz){ return-1; } auto[x,pref] =Base::prefix_lower_bound((int)order); return x*word+kth_set_bit(bits.word(x),order-pref); } size_t lower_bound(size_t x)const{ if(bits.test(x)){return x;} auto order=order_of_key(x); return order<sz?find_by_order(order): -1; } size_t pre_upper_bound(size_t x)const{ if(bits.test(x)){return x;} auto order=order_of_key(x); return order?find_by_order(order-1): -1; } }; }
Back to top page