Array Restoration [Codeforces Round #504 D]

http://codeforces.com/contest/1023/problem/D

1～Qの数から成るN要素の配列Aがある。
一部0となって、抜けている箇所がある。
0の部分を適切に埋めて、以下の操作によって配列Aが作れるか判定せよ。
作れるなら、0を適切に埋めて答えよ。
「iを1からQまで順番に使い、配列のある区間をiで埋める（区間の長さは1以上である必要がある）」

考察過程

1. 駄目な条件について考えてみると、ある数iの間にi未満の数があるとおかしい
2. その条件だけで駄目なパターンは網羅できそう（未証明）
3. 0の部分は横の数で埋めれば駄目な条件を壊さずに済む
4. コーナーケース「全て0」「Qが含まれていない」

解法

http://codeforces.com/contest/1023/submission/41779143

NOを判定しよう。2パターンある。

1パターン目の駄目な条件は「ある数iの間にi未満の数がある」ことである。
以下を用意する。
st.get(l, r) := A[l,r)の最小値（=0の要素は=infとして考える）
L[i] := ある数iが現れる添字の最小値
R[i] := ある数iが現れる添字の最大値
これで、st.get(L[i], R[i] + 1) < iであれば駄目な条件を満たすことになる。
　
2パターン目の駄目な条件は「0の要素が無く、Qである数が存在しない」ことである。
　
全てチェックして駄目でないことが分かれば、後は0を埋めていく。
0は隣の要素と同じものを使えば、駄目な条件を満たしてしまうことがない。
注意すべきなのが、Qが最低1つは必要なため、隣で0を埋めた後に、Qがなければ、どこか1つをQにすればいい。

int N, Q, A[201010];
int L[201010], R[201010];
SparseTable<int> st;
//---------------------------------------------------------------------------------------------------
#define yes "YES"
#define no "NO"
string solve() {
    int zero = 0;
    rep(i, 0, N) if (A[i] == 0) zero++;
    if (zero == N) {
        rep(i, 0, N) A[i] = Q;
        return yes;
    }

    vector<int> v;
    rep(i, 0, N) {
        if (A[i] == 0) v.push_back(inf);
        else v.push_back(A[i]);
    }
    st.init(v);

    rep(i, 1, Q + 1) L[i] = -1;
    rep(i, 0, N) if (A[i]) {
        if (L[A[i]] < 0) L[A[i]] = R[A[i]] = i;
        else {
            chmin(L[A[i]], i);
            chmax(R[A[i]], i);
        }
    }

    rep(q, 1, Q + 1) if (0 <= L[q]) if (st.get(L[q], R[q] + 1) < q) return no;

    int zidx = -1;
    rep(i, 0, N) if (!A[i]) zidx = i;

    if (zidx < 0) {
        int ma = -1;
        rep(i, 0, N) chmax(ma, A[i]);
        if (ma == Q) return yes;
        return no;
    }

    queue<int> que;
    rep(i, 0, N) if (A[i]) que.push(i);
    while (!que.empty()) {
        int q = que.front(); que.pop();

        if (q) if (A[q - 1] == 0) {
            A[q - 1] = A[q];
            que.push(q - 1);
        }

        if (q + 1 < N) if (A[q + 1] == 0) {
            A[q + 1] = A[q];
            que.push(q + 1);
        }
    }

    int ma = -1;
    rep(i, 0, N) chmax(ma, A[i]);
    if (ma < Q) A[zidx] = Q;
    return yes;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];

    string res = solve();
    printf("%s\n", res.c_str());
    if (res == no) return;

    rep(i, 0, N) {
        if (i) printf(" ");
        printf("%d", A[i]);
    }
    printf("\n");
}