典题合集

前置芝士

[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());
		}
	}
};