ソート列の隣接二項間の積を管理する
(Src/DataStructure/Other/SortedAdjacentProduct.hpp)

• View this file on GitHub
• Last update: 2024-07-27 05:40:09+09:00
• Include: #include "Src/DataStructure/Other/SortedAdjacentProduct.hpp"

概要

多重集合$S$がある。はじめ$S$は空である。$S$に対して以下のクエリを処理できる。

• $S$に要素$x$を挿入する。
• $S$中の$x$を一つ削除する。$x\in S$が必要である。
• $S$の各要素を昇順に並べた列を$A = (A_1, A_2, \dots, A_K)$とする。$f(A_{1}, A_{2}), f(A_{2}, A_{3}), \dots, f(A_{K - 1}, A_{K})$を管理する。

現状$f$としてxorを使う場合がプロコンで出題されている。

• $\min A_{i} \oplus A_{i + 1} = \min_{u\in S, v\in S} u\oplus v$が成り立つから

Depends on

• 標準データ型のエイリアス (Src/Template/TypeAlias.hpp)

Verified with

• Test/AtCoder/abc308_g.test.cpp
• Test/CF/CF956-F.test.cpp

Code

#pragma once

#include <cassert>
#include <iterator>
#include <set>
#include <utility>

#include "../../Template/TypeAlias.hpp"

namespace zawa {

template <class S>
class SortedAdjacentProduct {
public:
    using V = typename S::Element;
    using Iterator = typename std::multiset<V>::const_iterator;

    SortedAdjacentProduct() = default;

    SortedAdjacentProduct(const SortedAdjacentProduct<S>& sap) 
        : set_{sap.set_}, adj_{sap.adj_} {}

    SortedAdjacentProduct(SortedAdjacentProduct<S>&& sap)
        : set_{std::move(sap.set_)}, adj_{std::move(sap.adj_)} {}

    inline usize size() const noexcept {
        return set_.size();
    }

    inline bool empty() const noexcept {
        return set_.empty();
    }

    const std::multiset<V>& set() const noexcept {
        return set_;
    }

    const std::multiset<V>& adjacents() const noexcept {
        return adj_;
    }

    V min() const noexcept {
        assert(size() >= usize{2});
        return *adj_.cbegin();
    }

    V max() const noexcept {
        assert(size() >= usize(2));
        return *adj_.crbegin();
    }

    void insert(const V& v) {
        Iterator it{set_.lower_bound(v)};
        if (it != set_.end() and it != set_.begin()) {
            V val{S::operation(*std::prev(it), *it)};
            assert(eraseAdj(val));
        }
        if (it != set_.end()) {
            adj_.insert(S::operation(v, *it));
        }
        if (it != set_.begin()) {
            adj_.insert(S::operation(*std::prev(it), v));
        }
        set_.insert(v);
    }

    void erase(const V& v) {
        auto it{set_.lower_bound(v)};
        assert(it != set_.end() and *it == v);
        if (it != set_.begin()) {
            V val{S::operation(*std::prev(it), *it)};
            assert(eraseAdj(val));
        }
        if (std::next(it) != set_.end()) {
            V val{S::operation(*it, *std::next(it))};
            assert(eraseAdj(val));
        }
        if (it != set_.begin() and std::next(it) != set_.end()) {
            V val{S::operation(*std::prev(it), *std::next(it))};
            adj_.insert(val);
        }
        set_.erase(it);
    }

    bool contains(const V& v) {
        return set_.find(v) != set_.end();
    }

private:
    std::multiset<V> set_, adj_;

    bool eraseAdj(const V& v) {
        auto it{adj_.find(v)};
        bool res{it != adj_.end()};
        if (res) adj_.erase(it);
        return res;
    }
};

} // namespace zawa

#line 2 "Src/DataStructure/Other/SortedAdjacentProduct.hpp"

#include <cassert>
#include <iterator>
#include <set>
#include <utility>

#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 9 "Src/DataStructure/Other/SortedAdjacentProduct.hpp"

namespace zawa {

template <class S>
class SortedAdjacentProduct {
public:
    using V = typename S::Element;
    using Iterator = typename std::multiset<V>::const_iterator;

    SortedAdjacentProduct() = default;

    SortedAdjacentProduct(const SortedAdjacentProduct<S>& sap) 
        : set_{sap.set_}, adj_{sap.adj_} {}

    SortedAdjacentProduct(SortedAdjacentProduct<S>&& sap)
        : set_{std::move(sap.set_)}, adj_{std::move(sap.adj_)} {}

    inline usize size() const noexcept {
        return set_.size();
    }

    inline bool empty() const noexcept {
        return set_.empty();
    }

    const std::multiset<V>& set() const noexcept {
        return set_;
    }

    const std::multiset<V>& adjacents() const noexcept {
        return adj_;
    }

    V min() const noexcept {
        assert(size() >= usize{2});
        return *adj_.cbegin();
    }

    V max() const noexcept {
        assert(size() >= usize(2));
        return *adj_.crbegin();
    }

    void insert(const V& v) {
        Iterator it{set_.lower_bound(v)};
        if (it != set_.end() and it != set_.begin()) {
            V val{S::operation(*std::prev(it), *it)};
            assert(eraseAdj(val));
        }
        if (it != set_.end()) {
            adj_.insert(S::operation(v, *it));
        }
        if (it != set_.begin()) {
            adj_.insert(S::operation(*std::prev(it), v));
        }
        set_.insert(v);
    }

    void erase(const V& v) {
        auto it{set_.lower_bound(v)};
        assert(it != set_.end() and *it == v);
        if (it != set_.begin()) {
            V val{S::operation(*std::prev(it), *it)};
            assert(eraseAdj(val));
        }
        if (std::next(it) != set_.end()) {
            V val{S::operation(*it, *std::next(it))};
            assert(eraseAdj(val));
        }
        if (it != set_.begin() and std::next(it) != set_.end()) {
            V val{S::operation(*std::prev(it), *std::next(it))};
            adj_.insert(val);
        }
        set_.erase(it);
    }

    bool contains(const V& v) {
        return set_.find(v) != set_.end();
    }

private:
    std::multiset<V> set_, adj_;

    bool eraseAdj(const V& v) {
        auto it{adj_.find(v)};
        bool res{it != adj_.end()};
        if (res) adj_.erase(it);
        return res;
    }
};

} // namespace zawa

Back to top page