ABC179 F - Simplified Reversi
問題
解法
各行(列)の中で、最も左(上)側にある白マスの位置を効率よく管理する。
ax[i]:i行目で最も左側にある白マスの座標 ay[i]:i列目で最も上側にある白マスの座標
入力例1での説明。初期状態では、白マスはそれぞれ行列の右下端の置かれている。
1つの目のクエリ(1,3)を処理する。3列目の白マスで最も上側にあるのは5行目なので、 2~4行目までの黒マスを白マスに変える。その後、白マスが置かれた1~4行目に対して、axを更新する。
2つの目のクエリ(2,3)を処理する。3行目の白マスで最も上側にあるのは3列目なので、 1~2列目までの黒マスを白マスに変える。その後、白マスが置かれた1~2列目に対して、ayを更新する。
3番目、4番目のクエリも同様に処理する
全体の黒マスから白マスになった個数を引いていけば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; }