典题合集
前置芝士
[Set做法]
struct Mex {//自定义N的大小
int cnt[N];//cnt(i)表示数字i出现的次数
set<int> st;//记录未出现的数字
multiset<int> mulst;//记录出现过的数字
Mex() {
for (int i = 0; i < N; ++i) cnt[i] = 0;
for (int i = 0; i < N; ++i) st.insert(i);
}
void add(int x) {
//第一次添加
if (cnt[x] == 0) {
st.erase(x);
}
++cnt[x];
mulst.insert(x);
}
void del(int x) {
//只剩一个了
if (cnt[x] == 1) {
st.insert(x);
}
--cnt[x];
//不能写成mulst.erase(x) 这样是删除所有值为x的元素
mulst.erase(mulst.find(x));
}
int get_mx() {
return *st.begin();
}
void clear() {
while (!mulst.empty()) {
del(*mulst.begin());
}
}
};