1点更新・全体の mex 取得
(src/data_structures/mex-update.hpp)

• View this file on GitHub
• Last update: 2026-10-12 19:23:31+09:00
• Include: #include "src/data_structures/mex-update.hpp"

長さ $n$ の数列について、1点更新と、全体の mex (含まれない最小の非負整数) の取得を行います。

MexUpdate<int> mex(std::vector<int>{0, 1, 3});
int a = mex.prod();   // 2
mex.set(1, 5);        // {0, 5, 3}
int b = mex.prod();   // 1

メンバ関数

関数	説明	計算量
MexUpdate<T>(n)	長さ n で、どの要素もまだ値を持たない (mex は 0)	$O(n)$
MexUpdate<T>(v)	v で初期化	$O(n \log n)$
set(k, x)	k 番目を x に更新	$O(\log n)$
prod()	全体の mex	$O(1)$

負の値や $n$ より大きい値も入れられます (mex には影響しません)。

Verified with

• test/unittest/mex-update.test.cpp

Code

#pragma once

/**
 * @file mex-update.hpp
 * @brief 1点更新・全体の mex 取得
 */

#include <cassert>
#include <limits>
#include <map>
#include <set>
#include <vector>

template <typename T>
struct MexUpdate {
    using value_type = T;

   private:
    inline constexpr static value_type e = std::numeric_limits<value_type>::max();

    int n;
    std::vector<value_type> v;
    std::set<int> s;
    std::map<int, size_t> m;

   public:
    MexUpdate() = default;
    MexUpdate(int n) : n(n), v(n, e) {
        assert(n > 0);
        assert(n + 1 < e);
        std::set<int>::iterator hint = s.end();
        for (int i = n; i >= 0; --i) {
            hint = s.emplace_hint(hint, i);
        }
    }
    MexUpdate(const std::vector<value_type>& init) : n(init.size()), v(init) {
        assert(n > 0);
        assert(n + 1 < e);
        std::set<int>::iterator hint = s.end();
        for (int i = n; i >= 0; --i) {
            hint = s.emplace_hint(hint, i);
        }
        for (const auto& i : init) {
            if (0 <= i and i <= n) {
                m[i]++;
                s.erase(i);
            }
        }
    }
    void set(int k, const value_type& x) {
        assert(0 <= k and k < n);
        if (0 <= v[k] and v[k] <= n) {
            int v_k = v[k];
            auto itr = m.find(v_k);
            if (itr->second > 1) {
                itr->second--;
            } else {
                m.erase(itr);
                s.insert(v_k);
            }
        }
        if (0 <= x and x <= n) {
            int xx = x;
            auto itr = m.find(xx);
            if (itr == m.end()) {
                m[xx]++;
                s.erase(xx);
            } else {
                itr->second++;
            }
        }
        v[k] = x;
    }
    value_type prod() const {
        return *s.begin();
    }
};

#line 2 "src/data_structures/mex-update.hpp"

/**
 * @file mex-update.hpp
 * @brief 1点更新・全体の mex 取得
 */

#include <cassert>
#include <limits>
#include <map>
#include <set>
#include <vector>

template <typename T>
struct MexUpdate {
    using value_type = T;

   private:
    inline constexpr static value_type e = std::numeric_limits<value_type>::max();

    int n;
    std::vector<value_type> v;
    std::set<int> s;
    std::map<int, size_t> m;

   public:
    MexUpdate() = default;
    MexUpdate(int n) : n(n), v(n, e) {
        assert(n > 0);
        assert(n + 1 < e);
        std::set<int>::iterator hint = s.end();
        for (int i = n; i >= 0; --i) {
            hint = s.emplace_hint(hint, i);
        }
    }
    MexUpdate(const std::vector<value_type>& init) : n(init.size()), v(init) {
        assert(n > 0);
        assert(n + 1 < e);
        std::set<int>::iterator hint = s.end();
        for (int i = n; i >= 0; --i) {
            hint = s.emplace_hint(hint, i);
        }
        for (const auto& i : init) {
            if (0 <= i and i <= n) {
                m[i]++;
                s.erase(i);
            }
        }
    }
    void set(int k, const value_type& x) {
        assert(0 <= k and k < n);
        if (0 <= v[k] and v[k] <= n) {
            int v_k = v[k];
            auto itr = m.find(v_k);
            if (itr->second > 1) {
                itr->second--;
            } else {
                m.erase(itr);
                s.insert(v_k);
            }
        }
        if (0 <= x and x <= n) {
            int xx = x;
            auto itr = m.find(xx);
            if (itr == m.end()) {
                m[xx]++;
                s.erase(xx);
            } else {
                itr->second++;
            }
        }
        v[k] = x;
    }
    value_type prod() const {
        return *s.begin();
    }
};

Back to top page