Mex related learning

MEX Is the smallest positive integer that does not appear in an interval .

Therefore, adding a number to the interval is only for those who join the interval mex Value can be increased ;

Let's look at two topics

Problem - C - Codeforceshttps://codeforces.com/contest/1699/problem/C First of all, we can think about an interval 【L,R】 Of mex yes x, explain 【0,x-1】 It must have happened , So if x If the position of is inside the interval, it can be at any unused position in the interval , If you are not in this range, you can only stay in that position , because x Once moved, the sequence Column mex The value will definitely be affected .

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

Then there is this question We need to find the largest lexicographic sequence we can get , So we b The element obtained in the sequence must be the largest one that can be selected mex, So we can maintain a prefix mex And suffixes mex, When our prefix mex This is equal to the maximum mex The answer array can be added when , Then start directly from the next point mex Replace value with suffix mex Value

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');
}