online mex
(data_structure/online_mex.hpp)

• View this file on GitHub
• Last update: 2023-10-19 17:23:00+09:00
• Include: #include "data_structure/online_mex.hpp"
• Link: https://twitter.com/noshi91/status/1283759174791372809

説明

onlineで追加された値の集合のmexを計算する。

add(x)

非負整数 $x$ を集合に追加する。 amortized $O(1)$

mex()

集合のmexを返す。 amortized $O(1)$

size()

追加した値の個数を返す。 $O(1)$

Code

#pragma once

/*
    reference: https://twitter.com/noshi91/status/1283759174791372809

    Query
    add(int x) : amortized O(1)
    mex : amortized O(1)
*/

#include <vector>

namespace ebi {

struct online_mex {
  private:
    int mex_ = 0;
    int q = 0;
    int k = 1;
    std::vector<int> ret;
    std::vector<int> p;

    void update_mex() {
        while (ret[mex_] > 0) {
            mex_++;
        }
    }

    void increment() {
        q++;
        if (q < k) return;
        k *= 2;
        ret.assign(k, 0);
        for (const auto &val : p) {
            if (val < k) ret[val]++;
        }
    }

  public:
    online_mex() : ret(1, 0) {}

    void add(int x) {
        p.emplace_back(x);
        if (x < k) {
            ret[x]++;
        }
        increment();
    }

    int mex() {
        update_mex();
        return mex_;
    }

    int size() const {
        return p.size();
    }
};

}  // namespace ebi

#line 2 "data_structure/online_mex.hpp"

/*
    reference: https://twitter.com/noshi91/status/1283759174791372809

    Query
    add(int x) : amortized O(1)
    mex : amortized O(1)
*/

#include <vector>

namespace ebi {

struct online_mex {
  private:
    int mex_ = 0;
    int q = 0;
    int k = 1;
    std::vector<int> ret;
    std::vector<int> p;

    void update_mex() {
        while (ret[mex_] > 0) {
            mex_++;
        }
    }

    void increment() {
        q++;
        if (q < k) return;
        k *= 2;
        ret.assign(k, 0);
        for (const auto &val : p) {
            if (val < k) ret[val]++;
        }
    }

  public:
    online_mex() : ret(1, 0) {}

    void add(int x) {
        p.emplace_back(x);
        if (x < k) {
            ret[x]++;
        }
        increment();
    }

    int mex() {
        update_mex();
        return mex_;
    }

    int size() const {
        return p.size();
    }
};

}  // namespace ebi

Back to top page