misc/mex.hpp

• View this file on GitHub
• Last update: 2023-08-13 15:15:35+07:00
• Include: #include "misc/mex.hpp"

Code

class Mex {
 private:
  map<int, int> frequency;
  set<int> missing_numbers;
  vector<int> A;

 public:
  Mex(vector<int> const& A) : A(A) {
    for (int i = 0; i <= A.size(); i++) missing_numbers.insert(i);

    for (int x : A) {
      ++frequency[x];
      missing_numbers.erase(x);
    }
  }

  int mex() { return *missing_numbers.begin(); }

  void update(int idx, int new_value) {
    if (--frequency[A[idx]] == 0) missing_numbers.insert(A[idx]);
    A[idx] = new_value;
    ++frequency[new_value];
    missing_numbers.erase(new_value);
  }
};

#line 1 "misc/mex.hpp"
class Mex {
 private:
  map<int, int> frequency;
  set<int> missing_numbers;
  vector<int> A;

 public:
  Mex(vector<int> const& A) : A(A) {
    for (int i = 0; i <= A.size(); i++) missing_numbers.insert(i);

    for (int x : A) {
      ++frequency[x];
      missing_numbers.erase(x);
    }
  }

  int mex() { return *missing_numbers.begin(); }

  void update(int idx, int new_value) {
    if (--frequency[A[idx]] == 0) missing_numbers.insert(A[idx]);
    A[idx] = new_value;
    ++frequency[new_value];
    missing_numbers.erase(new_value);
  }
};

Back to top page