cp-documentation

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub zawa-tin/cp-documentation

:heavy_check_mark: 要素昇順 $K$ 個、降順 $N - K$ 個の総積を管理
(Src/DataStructure/Heap/PartitionedProducts.hpp)

いわゆる「Priority Queue二つ持ってガチャガチャやるやつ」。海外だとSmartSetなんて呼ばれているやつかも

ライブラリの使い方

内部で二つの削除可能Priority Queueを管理していて、昇順 $K$ 個を管理している方をsmall、他方をbigと呼ぶことにする。

テンプレート引数

template <class S, class T, class Comp = std::less<T>>
requires concepts::SetOperator<S, T> and std::strict_weak_order<Comp, const T&, const T&>
class PartitionedProducts

Sが総積の取り方を決める代数的構造。Tが各要素を意味する。

のみっつが定義されていれば良い。例えばかけざんならば、

struct OP {
    using Element = long long;
    static Element identity() {
        return 1;
    }
    static void add(Element& a, int x) {
        a *= x;
    }
    static void remove(Element& a, int x) {
        assert(a % x == 0);
        return a / x;
    }
};

で良い。このようにS::ElementとTは必ずしも同じ要素である必要は無い。

コンストラクタ

(1) PartitionedProducts(Comp comp = {}) 
(2) PartitionedProducts(std::vector<T> a, Comp comp = {})

compは指定しなければstd::less<T>になる。(std::less<T>以外のケースverifyしてないけど、ばぐってなければよいが…)

(2)においてaは全部small側に入る。

計算量: (2)は $O(N)$

size(), empty()

inline usize size() const
inline usize smallSize() const
inline usize bigSize() const
inline bool empty() const

insert

template <class U>
requires std::same_as<std::remove_cvref_t<U>, T>
void insert(U&& v)

なにやらややこしいが、T, const T&, T&&以外で使用することは基本的に想定されていない

計算量: $O(\log N)$

erase

template <class U>
requires std::same_as<std::remove_cvref_t<U>, T>
void erase(U&& v)

なにやらややこしいが、T, const T&, T&&以外で使用することは基本的に想定されていない

queに存在しない要素をeraseに呼んでもassertなどにはひっかからないが、後々のクエリでassert:Heap Underflowを発生させる。

計算量: $O(\log N)$

adjust

bool adjustSmall(usize K)
bool adjustBig(usize K)

それぞれ、small、bigの個数が $K$ になるように調節し、trueを返す。size() < Kのときはfalseを返し、何もしない。

top

const T& smallTop()
const T& bigTop()

呼び出す前にsmallSize(), bigSize()を確認しておくと良い。

計算量: ならし $O(1)$

prod

const S::Element& smallProd() const;
const S::Element& bigProd() const

計算量: $O(1)$

container

std::pair<std::vector<T>, std::vector<T>> container() const

デバッグ目的。firstにsmall, secondにbigがある。

Depends on

Verified with

Code

#pragma once

#include "EraseablePriorityQueue.hpp"
#include "../../Algebra/Action/SetOperator.hpp"

#include <utility>

namespace zawa {

namespace internal {

template <class Comp>
struct ReverseComp {

    [[no_unique_address]] Comp comp;

    ReverseComp() = default;

    explicit ReverseComp(Comp c) : comp(std::move(c)) {}

    template <class T, class U>
    bool operator()(T&& a, U&& b) const noexcept(noexcept(std::invoke(comp, std::forward<U>(b), std::forward<T>(a)))) {
        return std::invoke(comp, std::forward<U>(b), std::forward<T>(a));
    }
};

} // namespace internal

template <class S, class T, class Comp = std::less<T>>
requires concepts::SetOperator<S, T> and std::strict_weak_order<Comp, const T&, const T&>
class PartitionedProducts {
public:

    PartitionedProducts(Comp comp = {}) 
        : m_sm{internal::ReverseComp{comp}}, m_bg{comp}, m_comp{comp} {}

    PartitionedProducts(std::vector<T> a, Comp comp = {}) 
        : m_sm{}, m_bg{comp}, m_comp{comp} {
        for (const T& x : a)
            S::add(m_prodS, x);
        m_sm = EraseablePriorityQueue{std::move(a), internal::ReverseComp{comp}};
    }

    inline usize size() const {
        return m_sm.size() + m_bg.size();
    }

    inline usize smallSize() const {
        return m_sm.size();
    }

    inline usize bigSize() const {
        return m_bg.size();
    }

    inline bool empty() const {
        return m_sm.empty() and m_bg.empty();
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void insert(U&& v) {
        if (m_sm.empty())
            addBig(std::forward<U>(v));
        else if (m_bg.empty() or m_comp(v, m_bg.top()))
            addSmall(std::forward<U>(v));
        else
            addBig(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void erase(U&& v) {
        if (m_sm.empty())
            eraseBig(std::forward<U>(v));
        else if (m_bg.empty() or m_comp(v, m_bg.top()))
            eraseSmall(std::forward<U>(v));
        else
            eraseBig(std::forward<U>(v));
    }

    bool adjustSmall(usize K) {
        if (size() < K)
            return false;
        adjust(K);
        return true;
    }

    bool adjustBig(usize K) {
        if (size() < K)
            return false;
        adjust(size() - K);
        return true;
    }

    const T& smallTop() {
        assert(smallSize() and "HeapUnderFlow: small");
        return m_sm.top();
    }

    const S::Element& smallProd() const {
        return m_prodS;
    }

    const T& bigTop() {
        assert(bigSize() and "HeapUnderFlow: big");
        return m_bg.top();
    }

    const S::Element& bigProd() const {
        return m_prodB;
    }

    std::pair<std::vector<T>, std::vector<T>> container() const {
        return {m_sm.container(), m_bg.container()};
    }

private:

    EraseablePriorityQueue<T, internal::ReverseComp<Comp>> m_sm;

    EraseablePriorityQueue<T, Comp> m_bg;

    Comp m_comp;

    S::Element m_prodS = S::identity(), m_prodB = S::identity();

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void addSmall(U&& v) {
        S::add(m_prodS, v);
        m_sm.push(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void addBig(U&& v) {
        S::add(m_prodB, v);
        m_bg.push(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void eraseSmall(U&& v) {
        S::remove(m_prodS, v);
        m_sm.erase(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void eraseBig(U&& v) {
        S::remove(m_prodB, v);
        m_bg.erase(std::forward<U>(v));
    }

    void adjust(usize K) {
        while (smallSize() > K) {
            addBig(m_sm.top());
            S::remove(m_prodS, m_sm.top());
            m_sm.pop();
        }
        while (smallSize() < K) {
            addSmall(m_bg.top());
            S::remove(m_prodB, m_bg.top());
            m_bg.pop();
        }
    }
};

} // namespace zawa
#line 2 "Src/DataStructure/Heap/PartitionedProducts.hpp"

#line 2 "Src/DataStructure/Heap/EraseablePriorityQueue.hpp"

#line 2 "Src/DataStructure/Heap/BinaryHeap.hpp"

#line 2 "Src/Template/TypeAlias.hpp"

#include <cstdint>
#include <cstddef>

namespace zawa {

using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;

using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;

using usize = std::size_t;

} // namespace zawa
#line 4 "Src/DataStructure/Heap/BinaryHeap.hpp"

#include <algorithm>
#include <cassert>
#include <concepts>
#include <utility>
#include <vector>
#include <functional>

namespace zawa {

template <class T, class Comp = std::less<T>>
requires std::strict_weak_order<Comp, const T&, const T&>
class BinaryHeap {
private:

    Comp m_comp;

    std::vector<T> m_dat;

public:

    inline usize size() const {
        return m_dat.size() - 1;
    }

    inline bool empty() const {
        return m_dat.size() == 1;
    }

    inline const Comp& comp() const {
        return m_comp;
    }

    using const_iterator = typename decltype(m_dat)::const_iterator;

    const_iterator begin() const {
        return m_dat.begin() + 1;
    }

    const_iterator end() const {
        return m_dat.end();
    }

    BinaryHeap(Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {}

    template <std::forward_iterator It>
    requires std::same_as<std::iter_value_t<It>, T>
    BinaryHeap(It first, It last, Comp comp = {}) 
        : m_comp{comp}, m_dat(1) {
        m_dat.insert(m_dat.end(), first, last);
        build();
    }

    BinaryHeap(std::vector<T>&& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(std::make_move_iterator(a.begin()), std::make_move_iterator(a.end()), m_dat.begin() + 1);
        build();
    }

    BinaryHeap(const std::vector<T>& a, Comp comp = {}) 
        : m_comp{comp}, m_dat(a.size() + 1) {
        std::ranges::copy(a.begin(), a.end(), m_dat.begin() + 1);
        build();
    }

    const T& top() const {
        assert(size() and "HeapUnderFlow");
        return m_dat[1];
    }

    void push(T&& v) {
        m_dat.push_back(std::move(v));
        upHeap(size());
    }

    void push(const T& v) {
        m_dat.push_back(v);
        upHeap(size());
    }

    void pop() {
        assert(size() and "HeapUnderFlow");
        if (size() > 1)
            std::swap(m_dat[1], m_dat.back());
        m_dat.pop_back();
        if (size() > 1)
            downHeap(1, size());
    }

private:

    void build() {
        const usize n = size();
        for (usize i = (n >> 1) ; i ; i--) 
            downHeap(i, n);
    }

    void upHeap(usize i) {
        while (i >> 1 and m_comp(m_dat[i], m_dat[i >> 1])) {
            std::swap(m_dat[i], m_dat[i >> 1]);
            i >>= 1;
        }
    }

    void downHeap(usize i, usize n) {
        while ((i << 1) <= n) {
            usize j = i << 1;
            if (j + 1 <= n and m_comp(m_dat[j + 1], m_dat[j]))
                j++;
            if (!m_comp(m_dat[j], m_dat[i]))
                break;
            std::swap(m_dat[i], m_dat[j]);
            i = j;
        }
    }
};

} // namespace zawa
#line 4 "Src/DataStructure/Heap/EraseablePriorityQueue.hpp"

namespace zawa {

template <class T, class Comp = std::less<T>>
requires std::strict_weak_order<Comp, const T&, const T&>
class EraseablePriorityQueue {
private:

    BinaryHeap<T, Comp> m_que, m_rm;

    usize m_cnt = 0;

public:

    inline usize size() const {
        return m_cnt;
    }

    inline bool empty() const {
        return m_cnt == 0;
    }

    EraseablePriorityQueue(Comp comp = {}) 
        : m_que{comp}, m_rm{comp}, m_cnt{0} {}

    template <std::forward_iterator It>
    requires std::same_as<std::iter_value_t<It>, T>
    EraseablePriorityQueue(It first, It last, Comp comp = {})
        : m_que{first, last, comp}, m_rm{comp}, m_cnt{m_que.size()} {}

    EraseablePriorityQueue(std::vector<T> a, Comp comp = {}) 
        : m_que{a, comp}, m_rm{comp}, m_cnt{m_que.size()} {}

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void push(U&& v) {
        m_que.push(std::forward<U>(v));
        m_cnt++;
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void erase(U&& v) {
        assert(size() and "HeapUnderFlow");
        m_rm.push(std::forward<U>(v));
        m_cnt--;
    }

    const T& top() {
        assert(size() and "HeapUnderFlow");
        normalize();
        return m_que.top();
    }

    T pop() {
        assert(size() and "HeapUnderFlow");
        normalize();
        T res = m_que.top();
        m_que.pop();
        m_cnt--;
        return res;
    }

    std::vector<T> container() const {
        BinaryHeap que = m_que, rm = m_rm;  
        std::vector<T> res;
        while (que.size()) {
            if (rm.empty() or que.comp()(que.top(), rm.top())) {
                res.push_back(que.top());
                que.pop();
            }
            else if (que.top() == rm.top())
                que.pop(), rm.pop();
            else
                rm.pop();
        }
        return res;
    }

private:

    void normalize() {
        while (m_rm.size() and m_que.size()) {
            if (m_que.top() == m_rm.top())
                m_que.pop(), m_rm.pop();
            else if (m_que.comp()(m_rm.top(), m_que.top()))
                m_rm.pop();
            else
                break;
        }
    }
};

} // namespace zawa
#line 2 "Src/Algebra/Action/SetOperator.hpp"

#line 4 "Src/Algebra/Action/SetOperator.hpp"

namespace zawa {

namespace concepts {

template <class S, class T>
concept SetOperator = requires {
    typename S::Element;
    { S::identity() } -> std::same_as<typename S::Element>;
    { S::add(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
    { S::remove(std::declval<typename S::Element&>(), std::declval<T>()) } -> std::same_as<void>;
};

} // namespace concepts

} // namespace zawa
#line 5 "Src/DataStructure/Heap/PartitionedProducts.hpp"

#line 7 "Src/DataStructure/Heap/PartitionedProducts.hpp"

namespace zawa {

namespace internal {

template <class Comp>
struct ReverseComp {

    [[no_unique_address]] Comp comp;

    ReverseComp() = default;

    explicit ReverseComp(Comp c) : comp(std::move(c)) {}

    template <class T, class U>
    bool operator()(T&& a, U&& b) const noexcept(noexcept(std::invoke(comp, std::forward<U>(b), std::forward<T>(a)))) {
        return std::invoke(comp, std::forward<U>(b), std::forward<T>(a));
    }
};

} // namespace internal

template <class S, class T, class Comp = std::less<T>>
requires concepts::SetOperator<S, T> and std::strict_weak_order<Comp, const T&, const T&>
class PartitionedProducts {
public:

    PartitionedProducts(Comp comp = {}) 
        : m_sm{internal::ReverseComp{comp}}, m_bg{comp}, m_comp{comp} {}

    PartitionedProducts(std::vector<T> a, Comp comp = {}) 
        : m_sm{}, m_bg{comp}, m_comp{comp} {
        for (const T& x : a)
            S::add(m_prodS, x);
        m_sm = EraseablePriorityQueue{std::move(a), internal::ReverseComp{comp}};
    }

    inline usize size() const {
        return m_sm.size() + m_bg.size();
    }

    inline usize smallSize() const {
        return m_sm.size();
    }

    inline usize bigSize() const {
        return m_bg.size();
    }

    inline bool empty() const {
        return m_sm.empty() and m_bg.empty();
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void insert(U&& v) {
        if (m_sm.empty())
            addBig(std::forward<U>(v));
        else if (m_bg.empty() or m_comp(v, m_bg.top()))
            addSmall(std::forward<U>(v));
        else
            addBig(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void erase(U&& v) {
        if (m_sm.empty())
            eraseBig(std::forward<U>(v));
        else if (m_bg.empty() or m_comp(v, m_bg.top()))
            eraseSmall(std::forward<U>(v));
        else
            eraseBig(std::forward<U>(v));
    }

    bool adjustSmall(usize K) {
        if (size() < K)
            return false;
        adjust(K);
        return true;
    }

    bool adjustBig(usize K) {
        if (size() < K)
            return false;
        adjust(size() - K);
        return true;
    }

    const T& smallTop() {
        assert(smallSize() and "HeapUnderFlow: small");
        return m_sm.top();
    }

    const S::Element& smallProd() const {
        return m_prodS;
    }

    const T& bigTop() {
        assert(bigSize() and "HeapUnderFlow: big");
        return m_bg.top();
    }

    const S::Element& bigProd() const {
        return m_prodB;
    }

    std::pair<std::vector<T>, std::vector<T>> container() const {
        return {m_sm.container(), m_bg.container()};
    }

private:

    EraseablePriorityQueue<T, internal::ReverseComp<Comp>> m_sm;

    EraseablePriorityQueue<T, Comp> m_bg;

    Comp m_comp;

    S::Element m_prodS = S::identity(), m_prodB = S::identity();

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void addSmall(U&& v) {
        S::add(m_prodS, v);
        m_sm.push(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void addBig(U&& v) {
        S::add(m_prodB, v);
        m_bg.push(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void eraseSmall(U&& v) {
        S::remove(m_prodS, v);
        m_sm.erase(std::forward<U>(v));
    }

    template <class U>
    requires std::same_as<std::remove_cvref_t<U>, T>
    void eraseBig(U&& v) {
        S::remove(m_prodB, v);
        m_bg.erase(std::forward<U>(v));
    }

    void adjust(usize K) {
        while (smallSize() > K) {
            addBig(m_sm.top());
            S::remove(m_prodS, m_sm.top());
            m_sm.pop();
        }
        while (smallSize() < K) {
            addSmall(m_bg.top());
            S::remove(m_prodB, m_bg.top());
            m_bg.pop();
        }
    }
};

} // namespace zawa
Back to top page