それぞれの日に対して独立に答えを求める \(\mathrm{O}(N\log N)\) 解法と、次の日の答えを用いて上手く今日の答えを求める \(\mathrm{O}(N)\) 解法を解説します。

\(\mathrm{O}(N\log N)\) 解法

それぞれの \(i(1 \le i \le N)\) に対して、\((A_1,A_2,\dots,A_M)\) のうち \(i\) 以上の最小の値を求められれば良いです。

まず、「\(B_i = i\) 日目までに花火が上がる回数」という配列 \(B\) を累積和を用いて求めておくことで、\(l\) 日目から \(r\) 日目の間に花火が上がるか？を \(B_r - B_{l-1} \ge 1\) かどうかで \(\mathrm{O}(1)\) で判定できるようにしておきます。

すると、それぞれの \(i\) に対して二分探索を行うことで \(i\) 日目から \(x\) 日目までで花火が \(1\) 回以上上がる最小の \(x\) を \(\mathrm{O}(\log N)\) で求めることが出来ます。この \(x\) は \(i\) 日目以降で初めて花火が上がる日となります。よって、各 \(i\) に対してこれを行うことでこの問題を \(\mathrm{O}(N\log N)\) で解くことが出来ます。

もしくは、C++ であれば lower_bound を用いて直接求めることも出来ます。

\(\mathrm{O}(N)\) 解法

さて、まず \(N\) 日目に対しては答えは \(0\) 日後です。(\(N\) 日目には花火が上がることが保証されているため。)

ここで、\(i+1\) 日目の答えを \(x\) とした上で \(i\) 日目の答えを考えます。もし \(i\) 日目に花火が上がるのであれば答えは \(0\) 日後です。そうでないならば、答えは \(x+1\) 日後となります。

よって、上記を \(i=N-1,N-2,\dots,2,1\) 順に行うことで \(\mathrm{O}(N)\) で全ての \(i\) に対して答えを求めることが出来ます。

実装例(C++・\(\mathrm{O}(N\log N)\)・二分探索解)

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  for(int i=0;i<m;i++){
    cin>>a[i];
    a[i]--;
  }
  vector<int> b(n+1);
  for(int i=0;i<m;i++) b[a[i]+1]++;
  for(int i=1;i<=n;i++) b[i]+=b[i-1];
  for(int i=0;i<n;i++){
    int ok=n,ng=i-1;
    while(abs(ok-ng)>1){
      int mid=(ok+ng)/2;
      if(b[mid+1]-b[i]>=1) ok=mid;
      else ng=mid;
    }
    cout<<ok-i<<endl;
  }
}

実装例(C++・\(\mathrm{O}(N\log N)\)・lower_bound 解)

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  for(int i=0;i<m;i++){
    cin>>a[i];
    a[i]--;
  }
  for(int i=0;i<n;i++){
    int x=*lower_bound(a.begin(),a.end(),i);
    cout<<x-i<<endl;
  }
}

実装例(C++・\(\mathrm{O}(N)\) 解)

#include <bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin>>n>>m;
  vector<int> a(m);
  for(int i=0;i<m;i++){
    cin>>a[i];
    a[i]--;
  }
  vector<int> b(n);
  for(int i=0;i<m;i++){
    b[a[i]]=1;
  }
  vector<int> ans(n);
  for(int i=n-1;i>=0;i--){
    if(b[i]){
      ans[i]=0;
    }
    else{
      ans[i]=ans[i+1]+1;
    }
  }
  for(int i=0;i<n;i++) cout<<ans[i]<<endl;
}