P4137 Rmq Problem / mex (莫队)
程序员文章站
2022-06-25 16:01:09
题目 "P4137 Rmq Problem / mex" 解析 莫队算法维护mex, 往里添加数的时候,若添加的数等于$mex$,$mex$就不能等于这个值了,就从这个数开始枚举找$mex$;若不等于$mex$,没有影响. 取出数的时候,如果这个数出现的次数变为了$0$,$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; }