mex！！！それにしても、ならし計算量解析系が来たのびっくり！

問題概要

長さ $N$ の数列 $p_{1}, \dots, p_{N}$ が与えられる。

各 $i = 1, 2, \dots, N$ に対して、0 以上の整数で $p_{1}, \dots, p_{i}$ のいずれとも等しくない値のうち最小値を求めよ。

制約

$N, p_{i} \le 2 \times 10^{5}$

考えたこと

とりあえず次のような配列を用意したくなる。

exist[ v ] := これまで見てきた中に v という値はあるかどうかを表すブール値

これを用いて、次のように実装したくなる。つまり、

「res：現状の p には含まれてない値の最小値」としておいて
もし p[ i ] が登場したことによって、res が潰されたとしたら
res が潰されてないところまで ++res する

という論理だ。

int res = 0; // 初期状態では数値はまったくないので答えは 0
for (int i = 0; i < N; ++i) {
    exist[p[i]] = true;
    while (exist[cur]) ++res;

    cout << res << endl;
}

一見するとこれは $O(N^{2})$ かかるような気がしてしまうかもしれない。しかしなんと、これは $O(N)$ なのだ！(灰色 diff なのは、計算量を意識せずにこのようなコードを書いて通ってしまった人も多かったのかもしれない)

さて、似て非なるコードだけど、次のような書き方をしたら $O(N^{2})$ となってしまう。

for (int i = 0; i < N; ++i) {
    exist[p[i]] = true;
    int res = 0;
    while (exist[res]) ++res;

    cout << res << endl;
}

違いは res の扱い方にある。res の扱い方について、次のようになっている。

$O(N)$ にできているやつは、res の値を使い回している
$O(N^{2})$ になってしまっているやつは、res の値を毎回 0 からやり直している

ではなぜ、res の値を使い回すことで $O(N)$ になるのだろうか。確かに while 文によって res が一気に進むこともある。でも全体としてみると、res の値が $N+1$ を超えることはない。よって、

while (exist[res]) ++res;

という処理によって ++res がなされるのは、全体をとおしてみると、高々 $O(N)$ 回だけなのだ。このように「各 i に対する res が単調増加であることを利用して」「res の値を使い回す」ことによって、計算量を落とす考え方は、しゃくとり法などにも通じる！！！

なお、「全体を通してみると計算量は $O(N)$ 」というのは、言い換えると、1 回あたりのクエリには平均で $O(1)$ で処理できることを意味している。このような計算量を「ならし計算量」と呼ぶ。

コード

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

int main() {
    int N;
    cin >> N;
    vector<int> p(N);
    for (int i = 0; i < N; ++i) cin >> p[i];

    int cur = 0;
    vector<bool> exist(210000, false);
    for (int i = 0; i < N; ++i) {
        exist[p[i]] = true;
        while (exist[cur]) ++cur;
        cout << cur << endl;
    }
}