m1une's library

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

View on GitHub

:heavy_check_mark: Mex Multiset
(ds/bst/mex_multiset.hpp)

Overview

MexMultiset maintains multiplicities of integers in a fixed universe [0, U) and answers mex queries in constant time. It stores counts and uses a PredecessorSet to find the first missing value after updates, with deterministic bounds and $O(U)$ space.

Behavior

The returned answer is the smallest missing integer in [0, U), or U if all tracked values are present. It equals the actual mex whenever the actual mex is at most U. In particular, choosing U at least the maximum number of elements in the maintained collection always suffices. There is no automatic resizing.

Negative values and values at least U are ignored: insertion has no effect, erase returns false, and count returns 0. They are not stored. Repeated insertions increment multiplicity; erasure removes one occurrence. The mex can decrease only when the last occurrence of a tracked value is removed.

The vector constructor chooses U = values.size(). T must be a standard integral type, signed or unsigned, and the vector length must fit in int. The integer constructor asserts U >= 0. Each tracked multiplicity must fit in int; insertion asserts before overflowing it. Updates mutate the object; const queries do not mutate it.

Interface

Let $L = 1 + \lceil\log_{64}(U + 1)\rceil$.

Method Exact signature Description Complexity
Constructor MexMultiset() Constructs an empty universe (U = 0). $O(1)$
Constructor explicit MexMultiset(int universe_size) Constructs an empty multiset over [0, U). $O(U + 1)$
Constructor template <class T> explicit MexMultiset(const std::vector<T>& values) Constructs from values, with U = values.size(). $O(U + 1)$
universe_size int universe_size() const Returns U. $O(1)$
count int count(long long value) const Returns the tracked multiplicity, or 0 outside [0, U). $O(1)$
insert void insert(long long value) Adds one occurrence, or ignores an untracked value. $O(L)$ worst case; $O(1)$ for duplicates or untracked values
erase bool erase(long long value) Removes one occurrence and returns whether removal succeeded. $O(L)$ worst case; $O(1)$ unless the last occurrence is removed
mex int mex() const Returns the smallest missing value, capped at U. $O(1)$

Example

#include "ds/bst/mex_multiset.hpp"

#include <iostream>

int main() {
    m1une::ds::MexMultiset values(5);
    values.insert(0);
    values.insert(1);
    values.insert(1);
    values.insert(3);
    std::cout << values.mex() << '\n';  // 2

    values.erase(1);
    std::cout << values.mex() << '\n';  // 2: one copy of 1 remains
    values.erase(1);
    std::cout << values.mex() << '\n';  // 1
    values.insert(1);
    values.insert(2);
    std::cout << values.mex() << '\n';  // 4
}

Depends on

Verified with

Code

#ifndef M1UNE_DS_BST_MEX_MULTISET_HPP
#define M1UNE_DS_BST_MEX_MULTISET_HPP 1

#include <cassert>
#include <cstdint>
#include <limits>
#include <string>
#include <type_traits>
#include <vector>

#include "predecessor_set.hpp"

namespace m1une {
namespace ds {

// Tracks multiplicities in [0, U) and returns min(actual mex, U).
struct MexMultiset {
   private:
    std::vector<int> _count;
    PredecessorSet _missing;
    int _mex;

    static int checked_universe_size(int universe_size) {
        assert(universe_size >= 0);
        return universe_size;
    }

    static int checked_size(std::size_t size) {
        assert(size <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
        return int(size);
    }

   public:
    MexMultiset() : MexMultiset(0) {}

    explicit MexMultiset(int universe_size)
        : _count(checked_universe_size(universe_size), 0),
          _missing(std::string(universe_size, '1')), _mex(0) {}

    template <class T>
    explicit MexMultiset(const std::vector<T>& values)
        : _count(checked_size(values.size()), 0), _missing(0), _mex(0) {
        static_assert(
            std::is_integral_v<T> && sizeof(T) <= sizeof(std::uintmax_t),
            "MexMultiset requires standard integral values"
        );
        const int n = universe_size();
        for (T value : values) {
            if constexpr (std::is_signed_v<T>) {
                if (value < 0) continue;
            }
            if (static_cast<std::uintmax_t>(value) < static_cast<std::uintmax_t>(n)) {
                ++_count[int(value)];
            }
        }
        std::string membership(n, '1');
        for (int value = 0; value < n; ++value) {
            if (_count[value] != 0) membership[value] = '0';
        }
        _missing = PredecessorSet(membership);
        const int first = _missing.min();
        _mex = first == -1 ? n : first;
    }

    int universe_size() const {
        return int(_count.size());
    }

    int count(long long value) const {
        if (value < 0 || value >= universe_size()) return 0;
        return _count[int(value)];
    }

    void insert(long long value) {
        if (value < 0 || value >= universe_size()) return;
        const int key = int(value);
        assert(_count[key] < std::numeric_limits<int>::max());
        if (_count[key]++ != 0) return;
        _missing.erase(key);
        if (key == _mex) {
            const int first = _missing.min();
            _mex = first == -1 ? universe_size() : first;
        }
    }

    // Removes one occurrence; returns false for absent or untracked values.
    bool erase(long long value) {
        if (value < 0 || value >= universe_size()) return false;
        const int key = int(value);
        if (_count[key] == 0) return false;
        if (--_count[key] == 0) {
            _missing.insert(key);
            if (key < _mex) _mex = key;
        }
        return true;
    }

    int mex() const {
        return _mex;
    }
};

}  // namespace ds
}  // namespace m1une

#endif  // M1UNE_DS_BST_MEX_MULTISET_HPP
#line 1 "ds/bst/mex_multiset.hpp"



#include <cassert>
#include <cstdint>
#include <limits>
#include <string>
#include <type_traits>
#include <vector>

#line 1 "ds/bst/predecessor_set.hpp"



#include <bit>
#line 8 "ds/bst/predecessor_set.hpp"
#include <string_view>
#line 10 "ds/bst/predecessor_set.hpp"

namespace m1une {
namespace ds {

// Fixed-universe integer set with predecessor and successor queries.
struct PredecessorSet {
   private:
    static constexpr int word_bits = 64;

    int _universe_size;
    int _size;
    std::vector<std::vector<std::uint64_t>> _levels;

    static int checked_size(std::string_view membership) {
        assert(
            membership.size()
            <= static_cast<std::size_t>(std::numeric_limits<int>::max())
        );
        return int(membership.size());
    }

    int next_index(int index) const {
        if (index >= _universe_size) return _universe_size;
        for (int level = 0; level < int(_levels.size()); level++) {
            if (index / word_bits >= int(_levels[level].size())) break;
            std::uint64_t word =
                _levels[level][index / word_bits] >> (index % word_bits);
            if (word == 0) {
                index = index / word_bits + 1;
                continue;
            }
            index += int(std::countr_zero(word));
            for (int lower = level - 1; lower >= 0; lower--) {
                index *= word_bits;
                std::uint64_t lower_word =
                    _levels[lower][index / word_bits];
                index += int(std::countr_zero(lower_word));
            }
            return index;
        }
        return _universe_size;
    }

    int previous_index(int index) const {
        if (_universe_size == 0 || index < 0) return -1;
        if (index >= _universe_size) index = _universe_size - 1;
        for (int level = 0; level < int(_levels.size()); level++) {
            int offset = index % word_bits;
            std::uint64_t word = _levels[level][index / word_bits];
            if (offset != word_bits - 1) {
                word &= (std::uint64_t(1) << (offset + 1)) - 1;
            }
            if (word == 0) {
                index = index / word_bits - 1;
                if (index < 0) break;
                continue;
            }
            index += word_bits - 1 - int(std::countl_zero(word)) - offset;
            for (int lower = level - 1; lower >= 0; lower--) {
                index *= word_bits;
                std::uint64_t lower_word =
                    _levels[lower][index / word_bits];
                index += word_bits - 1 - int(std::countl_zero(lower_word));
            }
            return index;
        }
        return -1;
    }

    static int not_found_if_end(int index, int universe_size) {
        return index == universe_size ? -1 : index;
    }

   public:
    PredecessorSet() : PredecessorSet(0) {}

    explicit PredecessorSet(int universe_size)
        : _universe_size(universe_size), _size(0) {
        assert(universe_size >= 0);
        int length = universe_size == 0 ? 1 : universe_size;
        do {
            int words = int((std::int64_t(length) + word_bits - 1) / word_bits);
            _levels.emplace_back(words, 0);
            length = words;
        } while (length > 1);
    }

    explicit PredecessorSet(std::string_view membership)
        : PredecessorSet(checked_size(membership)) {
        for (int index = 0; index < _universe_size; index++) {
            assert(membership[index] == '0' || membership[index] == '1');
            if (membership[index] == '1') {
                _levels[0][index / word_bits]
                    |= std::uint64_t(1) << (index % word_bits);
                _size++;
            }
        }
        for (int level = 1; level < int(_levels.size()); level++) {
            for (int index = 0; index < int(_levels[level - 1].size()); index++) {
                if (_levels[level - 1][index] != 0) {
                    _levels[level][index / word_bits]
                        |= std::uint64_t(1) << (index % word_bits);
                }
            }
        }
    }

    int universe_size() const {
        return _universe_size;
    }

    int size() const {
        return _size;
    }

    bool empty() const {
        return _size == 0;
    }

    bool contains(int key) const {
        assert(0 <= key && key < _universe_size);
        return ((_levels[0][key / word_bits] >> (key % word_bits)) & 1U) != 0;
    }

    bool insert(int key) {
        assert(0 <= key && key < _universe_size);
        if (contains(key)) return false;
        int index = key;
        for (auto& level : _levels) {
            std::uint64_t& word = level[index / word_bits];
            bool was_empty = word == 0;
            word |= std::uint64_t(1) << (index % word_bits);
            if (!was_empty) break;
            index /= word_bits;
        }
        _size++;
        return true;
    }

    bool erase(int key) {
        assert(0 <= key && key < _universe_size);
        if (!contains(key)) return false;
        int index = key;
        for (auto& level : _levels) {
            std::uint64_t& word = level[index / word_bits];
            word &= ~(std::uint64_t(1) << (index % word_bits));
            if (word != 0) break;
            index /= word_bits;
        }
        _size--;
        return true;
    }

    // Returns the smallest key greater than or equal to key, or -1.
    int successor(int key) const {
        assert(0 <= key && key < _universe_size);
        return not_found_if_end(next_index(key), _universe_size);
    }

    // Returns the largest key less than or equal to key, or -1.
    int predecessor(int key) const {
        assert(0 <= key && key < _universe_size);
        return previous_index(key);
    }

    int min_ge(int key) const {
        return successor(key);
    }

    int min_gt(int key) const {
        assert(0 <= key && key < _universe_size);
        return not_found_if_end(next_index(key + 1), _universe_size);
    }

    int max_le(int key) const {
        return predecessor(key);
    }

    int max_lt(int key) const {
        assert(0 <= key && key < _universe_size);
        return previous_index(key - 1);
    }

    int min() const {
        return not_found_if_end(next_index(0), _universe_size);
    }

    int max() const {
        return previous_index(_universe_size - 1);
    }
};

}  // namespace ds
}  // namespace m1une


#line 12 "ds/bst/mex_multiset.hpp"

namespace m1une {
namespace ds {

// Tracks multiplicities in [0, U) and returns min(actual mex, U).
struct MexMultiset {
   private:
    std::vector<int> _count;
    PredecessorSet _missing;
    int _mex;

    static int checked_universe_size(int universe_size) {
        assert(universe_size >= 0);
        return universe_size;
    }

    static int checked_size(std::size_t size) {
        assert(size <= static_cast<std::size_t>(std::numeric_limits<int>::max()));
        return int(size);
    }

   public:
    MexMultiset() : MexMultiset(0) {}

    explicit MexMultiset(int universe_size)
        : _count(checked_universe_size(universe_size), 0),
          _missing(std::string(universe_size, '1')), _mex(0) {}

    template <class T>
    explicit MexMultiset(const std::vector<T>& values)
        : _count(checked_size(values.size()), 0), _missing(0), _mex(0) {
        static_assert(
            std::is_integral_v<T> && sizeof(T) <= sizeof(std::uintmax_t),
            "MexMultiset requires standard integral values"
        );
        const int n = universe_size();
        for (T value : values) {
            if constexpr (std::is_signed_v<T>) {
                if (value < 0) continue;
            }
            if (static_cast<std::uintmax_t>(value) < static_cast<std::uintmax_t>(n)) {
                ++_count[int(value)];
            }
        }
        std::string membership(n, '1');
        for (int value = 0; value < n; ++value) {
            if (_count[value] != 0) membership[value] = '0';
        }
        _missing = PredecessorSet(membership);
        const int first = _missing.min();
        _mex = first == -1 ? n : first;
    }

    int universe_size() const {
        return int(_count.size());
    }

    int count(long long value) const {
        if (value < 0 || value >= universe_size()) return 0;
        return _count[int(value)];
    }

    void insert(long long value) {
        if (value < 0 || value >= universe_size()) return;
        const int key = int(value);
        assert(_count[key] < std::numeric_limits<int>::max());
        if (_count[key]++ != 0) return;
        _missing.erase(key);
        if (key == _mex) {
            const int first = _missing.min();
            _mex = first == -1 ? universe_size() : first;
        }
    }

    // Removes one occurrence; returns false for absent or untracked values.
    bool erase(long long value) {
        if (value < 0 || value >= universe_size()) return false;
        const int key = int(value);
        if (_count[key] == 0) return false;
        if (--_count[key] == 0) {
            _missing.insert(key);
            if (key < _mex) _mex = key;
        }
        return true;
    }

    int mex() const {
        return _mex;
    }
};

}  // namespace ds
}  // namespace m1une
Back to top page