せかいの世界(備忘録)

音楽・ITに関する色々なものを触ってみたり、競プロの記録を残したりします。

ABC179 F - Simplified Reversi

問題

atcoder.jp

解法

各行(列)の中で、最も左(上)側にある白マスの位置を効率よく管理する。

ax[i]:i行目で最も左側にある白マスの座標
ay[i]:i列目で最も上側にある白マスの座標 

入力例1での説明。初期状態では、白マスはそれぞれ行列の右下端の置かれている。

f:id:tori114:20201203004812p:plain:w400

1つの目のクエリ(1,3)を処理する。3列目の白マスで最も上側にあるのは5行目なので、 2~4行目までの黒マスを白マスに変える。その後、白マスが置かれた1~4行目に対して、axを更新する。

f:id:tori114:20201203005943p:plain:w400

2つの目のクエリ(2,3)を処理する。3行目の白マスで最も上側にあるのは3列目なので、 1~2列目までの黒マスを白マスに変える。その後、白マスが置かれた1~2列目に対して、ayを更新する。

f:id:tori114:20201203005415p:plain:w400

3番目、4番目のクエリも同様に処理する f:id:tori114:20201203010030p:plain:w400 f:id:tori114:20201203005624p:plain:w400

全体の黒マスから白マスになった個数を引いていけばOK

コード

int op(int a, int b){
  return min(a,b);
}

int e(){
  return (int)(1e9);
}

int main() {
  ll n,q;
  cin >> n >> q;
  atcoder::segtree<int, op, e> ax(n+1),ay(n+1);
  ax.set(n,n);
  ay.set(n,n); 
  ll ans = (n-2)*(n-2);
  while(q--){
    int t,p;
    cin >> t >> p;
    if(t == 1){
      int r = ax.prod(p,n+1);
      ans-=r-2;
      ay.set(r, min(ay.get(r),p));
    }
    else{
      int r = ay.prod(p,n+1);
      ans-=r-2;
      ax.set(r, min(ax.get(r),p));
    }
  }
  cout<<ans<<endl;
  return 0;
}