MEX有关的学习

MEX是一段区间内未出现的最小正整数。

所以向该区间加一个数只有加入该区间的mex值时才能增加；

我们来看两个题目

Problem - C - Codeforceshttps://codeforces.com/contest/1699/problem/C首先我们可以思考一个区间【L,R】的mex是x，说明【0，x-1】肯定都出现过了，所以如果x的位置在该区间内部则可以在区间内任意一个未被使用的位置，如果不在该区间内就只能在那个位置不动了，因为x一旦动那么该序列的mex值肯定会受到影响。

int a[MAXN];
int pos[MAXN];
const int mod = 1e9 + 7;
void solve() {
	int n;
	ll ans = 1;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
		pos[a[i]] = i;
	}
	int mx = -INF, mn = INF;
	for (int i = 0; i < n; i++) {
		if (pos[i] > mn && pos[i] < mx) {
			ans *= (mx - mn + 1 - i);
			ans %= mod;
		}
		mn = min(mn, pos[i]);
		mx = max(mx, pos[i]);
	}
	printf("%lld\n", ans);
}

 Problem - C - CodeforcesCodeforces. Programming competitions and contests, programming communityhttps://codeforces.com/contest/1629/problem/C

然后是这一题 需要求我们能得出得最大字典序序列，所以我们b序列中得到得元素肯定是能选到得最大得mex，所以我们可以维护一个前缀mex和后缀mex，当我们的前缀mex此时等于最大的mex时候就可以加入答案数组，然后直接从下一点开始把mex值替换成后缀mex的值

struct MEX {
	int cot[MAXN];
	vector<int> res;
	int id = 0;
	void add(int x) {
		cot[x]++;
		res.push_back(x);
	}
	int mex() {
		while (cot[id])
			id++;
		return id;
	}
	void clear() {
		for (int v : res) {
			cot[v]--;
		}
		id = 0;
		res.clear();
	}
};
MEX now, t;
int a[MAXN];
int last[MAXN];
 
void solve() {
	now.clear();
	t.clear();
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	for (int i = n; i >= 1; i--) {
		t.add(a[i]);
		last[i] = t.mex();
	}
	vector<int> ans;
	int mx = last[1];
	for (int i = 1; i <= n; i++) {
		now.add(a[i]);
		if (mx == now.mex()) {
			ans.push_back(mx);
			mx = last[i + 1];
			now.clear();
		}
	}
	printf("%d\n", ans.size());
	for (int v : ans) {
		printf("%d ", v);
	}
	putchar('\n');
}