問題原案：admin

様々な解法がありますが、ここではオンライン ( \(i+1\) 個目の入力を受け取らずして \(i\) 個目の解を求める ) での解法を示します。

まず、人が到着すると何が起こるかを検討しましょう。
左から \(k\) 番目に人が到着したとしましょう。
この時、「最も近い別の人までの距離」が変動する可能性があるのは、(たった今到着した人を含めて) 左から \(k-1\) 番目、 \(k\) 番目、 \(k+1\) 番目だけです (以降、この \(3\) 人を \(x,y,z\) と呼ぶことにします) 。
なので、人が到着しようと全員に対して再計算する必要はなく、この \(3\) 人に対してのみ更新を行えばよいです。

このように、影響のある点だけを再計算するテクニックは 差分更新 と呼ばれ、 Algorithm のみならず Heuristic でも効果的なものです。

以降、 \(2\) つの方針を示します。

方針1. 当該の \(3\) 人について、素直に差分更新する

以下の手順を使って差分更新できます。

• \(x,z\) について、 ( \(y\) の挿入前での ) 最も近い別の人までの距離を減算する。
• \(y\) を挿入する。
• \(x,y,z\) について、最も近い別の人までの距離を加算する。

方針2. 問題の特性を利用して、簡単に差分更新する

この問題の性質上、「最も近い別の人までの距離」は \(y\) の挿入によって増加することがありません。なので、以下の手順で差分更新できます。

• \(x,z\) については、「最も近い別の人までの距離」を \(y\) との距離と比較して、小さい方に更新する。
• \(y\) については、 \(x,z\) 近い方との距離に設定する。

方針1 は差分に特に良い性質がない時に、方針2は差分に良い性質があり計算量や実装量が削減できる時に有効なので、どちらも意識しておくと吉です。

以下の実装例について、どちらも時間計算量 \(O(N \log N)\) です。

方針1 実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int nearest(int x,set<int> &st){
  auto it=st.find(x);
  int res=2e9;
  if(it!=st.begin()){
    auto jt=it; jt--;
    res=min(res,x-(*jt));
  }
  it++;
  if(it!=st.end()){
    res=min(res,(*it)-x);
  }
  return res;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  int res=0;
  set<int> st;
  {
    int x;
    cin >> x;
    st.insert(0);
    st.insert(x);
    res+=2*x;
    cout << res << "\n";
  }
  for(int i=1;i<n;i++){
    int x;
    cin >> x;
    vector<int> hit;
    auto it=st.lower_bound(x);
    if(it!=st.end()){hit.push_back(*it);}
    if(it!=st.begin()){
      it--;
      hit.push_back(*it);
    }
    for(auto &nx : hit){
      res-=nearest(nx,st);
    }
    st.insert(x);
    hit.push_back(x);
    for(auto &nx : hit){
      res+=nearest(nx,st);
    }
    cout << res << "\n";
  }
  return 0;
}

方針2 実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int n;
  cin >> n;
  int res=0;
  set<int> st;
  map<int,int> mp;
  {
    int x;
    cin >> x;
    st.insert(0);
    st.insert(x);
    mp[0]=x;
    mp[x]=x;
    res+=2*x;
    cout << res << "\n";
  }
  for(int i=1;i<n;i++){
    int x;
    cin >> x;
    vector<int> hit;
    auto it=st.lower_bound(x);
    if(it!=st.end()){hit.push_back(*it);}
    if(it!=st.begin()){
      it--;
      hit.push_back(*it);
    }
    st.insert(x);
    mp[x]=2e9;
    for(auto &nx : hit){
      res-=mp[nx];
      mp[nx]=min(mp[nx],abs(nx-x));
      res+=mp[nx];
      mp[x]=min(mp[x],abs(nx-x));
    }
    res+=mp[x];
    cout << res << "\n";
  }
  return 0;
}

Bonus!
上記の例では答えを管理する変数が int 型 ( 上限約 \(2.1 \times 10^9\) ) となっていますが、問題ありません。何故でしょうか？