\(B\) に対して \(k=1,2,...,M\) の順に操作を行いながら、以下の情報を管理することを考えます。

• 各 \(i(1 \leq i \leq M)\) について、\(k=i\) の操作を飛ばした場合に現在 \(B_j=1\) を満たす \(j\) の値を \(D_i\) とする。
• 各 \(j(1 \leq j \leq N)\) について、\(D_i = j\) を満たす \(i\) の集合を \(S_j\) とする。この \(S_j\) を管理する。

各操作における \(S_j (1 \leq j \leq N)\) の更新は、集合の管理に std::set 等の平衡二分探索木を用いた場合 \(O(log N)\) で実行可能なため、\(O(N + M log N)\) でこの問題を解くことができます。

更新の仕方等の詳細については下記の実装例を参照してください。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m);
    for (int &i: a) {
        cin >> i;
    }
    
    // st[j] に i が含まれる
    //   <=> a[i] を無視して操作したとき、b[j] = 1
    vector <set<int>> st(n + 1);
    for (int i = 0; i < m; i++) {
        st[1].insert(i);
    }
    
    for (int i = 0; i < m; i++) {
        swap(st[a[i]], st[a[i] + 1]);
        if (st[a[i]].count(i)) {
            st[a[i]].erase(i);
            st[a[i] + 1].insert(i);
        } else if (st[a[i] + 1].count(i)) {
            st[a[i] + 1].erase(i);
            st[a[i]].insert(i);
        }
    }
    
    vector<int> ans(m);
    for (int i = 1; i <= n; i++) {
        for (int j: st[i]) ans[j] = i;
    }
    for (int i: ans) cout << i << '\n';
}