P4137 Rmq Problem / mex (莫队)

时间：2022-07-02 07:16:57

题目

P4137 Rmq Problem / mex

解析

莫队算法维护mex，

  • 往里添加数的时候，若添加的数等于\(mex\)，\(mex\)就不能等于这个值了，就从这个数开始枚举找\(mex\)；若不等于\(mex\)，没有影响，因为它之前的所有数都出现过了，又出现一次不会怎样，放在后面又比\(mex\)大，肯定不是\(mex\).
  • 取出数的时候，如果这个数出现的次数变为了\(0\)，\(mex\)就和这个数取一个\(min\)

代码

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6 + 10;

int n, m, mex;

int a[N], cnt[N], ans[N];

class node {

	public :

		int l, r, id, bl;

		bool operator < (const node &oth) const {

			return this->bl == oth.bl ? this->r < oth.r : this->l < oth.l;

		}

} e[N];

template<class T>inline void read(T &x) {

	x = 0; int f = 0; char ch = getchar();

	while (!isdigit(ch)) f |= (ch == '-'), ch = getchar();

	while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();

	x = f ? -x : x;

	return ;

} 

inline void add(int x) {

	cnt[a[x]]++;

	int i = mex;

	if (a[x] == mex) while (cnt[i]) i++;

	mex = i;

}

inline void del(int x) {

	cnt[a[x]]--;

	if (cnt[a[x]] == 0) mex = min(mex, a[x]);

}

int main() {

	read(n), read(m);

	int k = sqrt(n);

	for (int i = 1; i <= n; ++i) read(a[i]);

	for (int i = 1, x, y; i <= m; ++i) {

		read(x), read(y);

		e[i] = (node) {x, y, i, x / k + 1};

	}

	sort(e + 1, e + 1 + m);

	int l = 1, r = 0;

	for (int i = 1; i <= m; ++i) {

		int ll = e[i].l, rr = e[i].r;

		while (l < ll) del(l++);

		while (l > ll) add(--l);

		while (r < rr) add(++r);

		while (r > rr) del(r--);

		ans[e[i].id] = mex;

	}

	for (int i = 1; i <= m; ++i) printf("%d\n", ans[i]);

	return 0;

}

相关文章