Neq Min [HHKB プログラミングコンテスト 2020 C]

https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c

解説

https://atcoder.jp/contests/hhkb2020/submissions/17316773

こういったクエリ問題では、1クエリだけの場合ではどのように答えるかを考える。

i=Nの場合は？

いずれとも等しくない値で、かつ、最小値を求める一番愚直な方法として、
0から数列に含まれるかをチェックしていって、最初に含まれない数を答えるという方針がある。
この場合は、数列に含まれるかを高速に判定するためにsetを使用することができる。
数列に含まれる数字をすべてsetに追加し、0から順にsetに含まれているかを判定して、含まれていない数を答えるようにする。
これで計算量はO((pの最大値)logN)となる。

クエリにどう対応していくか

実はこの方針をいじることで答えにたどり着くことができる。
気づくべき性質が、各クエリの答えは広義単調増加するということである。
これはi=xの答え未満の数はi=x+1でも必ず存在していることに起因している。
よって、クエリ毎に0から順番に探索していく必要はなく、
i=x+1のクエリを処理するときは、i=xの時の答えから探索を始めることができる。
このような探索方針は尺取り法とかなり似ていて、本質的にはそれほど変わらない。

答えの方針

各クエリにおいて、setに数字を入れてから、前回の答えから探索を始める。
setに数が含まれないならその数を答えて次のクエリを処理し、そうでないなら、答えをインクリメントしていく。
計算量はO(((pの最大値)+N)logN)

int N, p[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> p[i];

    int ans = 0;
    set<int> ps;
    rep(i, 0, N) {
        ps.insert(p[i]);
        while (ps.count(ans)) ans++;
        printf("%d\n", ans);
    }
}