B. Sorting the Coins

1500 
// input
4
1 3 4 2

// output
1 2 3 2 1

f:id:peroon:20201207234755p:plain

  • 問題理解つづき
    • 最初の状態はOOOO
    • これで右までスキャンもカウントするので、この場合の答えは1
    • ＿
    • 次にいよいよ配列Pを使いはじめて、位置1をXにして、iを左から右に動かしつつ、XOならOXにする。これを何度やればもう動かない状態にできるかを答える
    • XOOOなので、スムーズにOOOXまで移動するので操作は1回、スキャンの1回と合わせて答えは2
    • ＿
    • 次は「1, 3」にXを置く
    • XOXOという状態
    • OXXO
    • OXOX 1回の操作でここまでXが動く。一連の操作をやるたびに（左から衝撃波をうつたびに）Xが右によっていく
    • もう1度やると、OOXXとなるので、衝撃波2回、スキャン1回の3が答え
    • これを答えていく
  • 解説
    • 各回の答えは、右に行ききったX以外のXの数+1(スキャン分)
    • たとえばOXOXOXOXXX
    • の場合、Xは6個あるが、右に行ききったXが3個あるのでそれを引き、3。スキャン分を合わせて4が答え
    • 「右にいききったXの数」は増える一方（単調性がある）ので、適切に数えられる
  • 証明？
    • まだ右に行ききっていないXを「浮いているX」と呼ぶことにする
    • (左から右までの)一連の操作1回で、浮いているXのうち1つだけが右端に達する。他は到達せずに途中で止まる（証明終わり）
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N; 
    cin>>N;

    VI A(N);
    rep(i, N) cin >> A[i];
    
    VI Ans={1};
    ll r=N+1;//右端の連続するXの左端
    VI C(N+10);
    rep(i,N){
      ll a = A[i];
      C[a]++;
      while(C[r-1]==1){
        r--;
      }
      // 右端Xの個数
      ll num = N-r;
      // 全体のXの個数
      ll all = i+1;
      // 右端以外のXの個数
      ll ans = all-num;
      Ans.push_back(ans);
    }
    print_vector(Ans);
    
    return 0;
}