Contest Duration: - (local time) (100 minutes) Back to Home
Official

## E - Add and Mex Editorial by en_translator

First, let us consider, given a sequence $$A$$ of length $$N$$, a simple problem of finding the minimum non-negative integer not contained in $$A$$.

Then, the answer is obviously between $$0$$ and $$N$$, so we can safely ignore the negative elements and the elements greater than $$N$$ in $$A$$, as it does not affect the answer.

Based on this observation, we can solve the original problem too. Let us call a value important if we cannot ignore it. How many important values are there?

There are at most $$N$$ values for $$i=1$$, at most $$\lceil\frac{N}{2}\rceil$$ values for $$i=2$$, … so, by the harmonic series, there are $$\mathrm{O}(N\log N)$$ important values in total.

Therefore, the sum of the answer is also about $$\mathrm{O}(N\log N)$$. Therefore, it is fast enough to find the answer for each output in a linear time of the answer.

Specifically, for each operation, we can check if there is $$0$$, there is $$1$$, …. See the sample code for how to store the data.

Sample code (C++):

#include <bits/stdc++.h>
using namespace std;

int main() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for(auto &v : a) cin >> v;
vector<vector<int>> vals(m + 1);
for(int i = 0; i < n; i++) {
if(a[i] >= n) continue;
int l = (a[i] >= 0 ? 1 : (-a[i] + i) / (i + 1));
int r = min(m + 1, (n - a[i] + i) / (i + 1));
for(int j = l; j < r; j++) {
vals[j].push_back(a[i] + (i + 1) * j);
}
}
for(int i = 1; i <= m; i++) {
int sz = vals[i].size();
vector<bool> exi(sz + 1);
for(auto v : vals[i]) {
if(v < sz) exi[v] = true;
}
int res = 0;
while(exi[res]) res++;
cout << res << endl;
}
}

posted:
last update: