This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub dnx04/algo
#include "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); } };
#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); } };