-
Notifications
You must be signed in to change notification settings - Fork 0
/
Mex_with_Update.cpp
66 lines (56 loc) · 1.23 KB
/
Mex_with_Update.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <bits/stdc++.h>
using namespace std;
// MEX with Update, build -> O(n*log(n)), update -> O(log(n))
template <typename T>
struct Mex {
vector<T> arr;
map<T, int> frequency;
set<T> missing_numbers;
Mex(const vector<T> &_arr) : arr(_arr) {
for (int i = 0; i <= (int)arr.size(); i++) {
missing_numbers.insert(i);
}
for (auto v : arr) {
frequency[v]++;
missing_numbers.erase(v);
}
}
void modify(int x, const T &v) {
assert(x < (int)arr.size());
if (--frequency[arr[x]] == 0) {
missing_numbers.insert(arr[x]);
}
arr[x] = v;
frequency[v]++;
missing_numbers.erase(v);
}
T get() {
return *missing_numbers.begin();
}
};
void solve() {
int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
Mex mex(a);
while (q--) {
int ind, x;
cin >> ind >> x;
ind--;
mex.modify(ind, x);
cout << mex.get() << '\n';
}
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
//cin >> t;
while (t--) {
solve();
}
return 0;
}