競技プログラミング 知識集積所

ABC461 E - E-liter

Eリットル (?)

問題ページ解答例

考え方

愚直にやると、盤面サイズが $O(N^2)$ で、それを用意する初期化処理だけでTLE。
そこで、問題を上手に言い換えてやることが必要になる。

座標 $(i,j)$ が白か黒かというのは、$i$ 行目と $j$ 列目で最後に塗られたのはどちらが後かということ。
つまり、クエリ一覧を以下の規則で文字列に変換することで、問題を言い換えられる。

そして、「全ての 'B' と 'W' の組について、'W' が先にあるものはいくつあるか」が言い換えとなる。
ただし、本当にこれだけだと一度も塗られていない行や列をうまく扱えない。
そこで、最初に「全ての行を $1$ 回ずつ塗る」の後に「全ての列を $1$ 回ずつ塗る」を行うことにする。
この $2N$ 個のクエリを事前に行うことで、一度も塗られていない行も列も存在しなくなる。
しかも本物のクエリは全面が白の状態で処理が開始されるため、問題は解消される。

あとは、言い換えた問題を解くだけだが、これはsegment木で解ける。
データとして、その範囲の「Bの個数、Wの個数、W→Bの組数」を持たせる。
単位元は {0,0,0}。
演算は、まず、Bの個数とWの個数は単純に加算。
W→Bの組数は、単純に加算したところに、左のW数と右のB数の積を加える。
クエリ数が $2N+Q$ 個になっていることに注意。

最初の $2N$ 個のクエリをセグ木に埋め込み、残り $Q$ 個は「受け取る、処理、解答」を繰り返せばよい。
その際、「そのクエリが来るまでは最後の塗りだった」ところをリセットする必要がある。
そのため、各行各列、最後に塗ったタイミングのタイムスタンプも持っておくこと。

計算量は $O((N+Q)\log(N+Q))$ である。

入力例1での動作

入力を受け取る。
行番号・列番号は、受け取った値から $1$ を引いて 0-indexed にしておく。

n: 3
q: 4
query:
  {1, 0}
  {1, 2}
  {2, 1}
  {1, 0}

最初に、全ての行を $1$ 回ずつ黒く塗り、その後に全ての列を $1$ 回ずつ白く塗ったことにする。

行の最終時刻: {0, 1, 2}
列の最終時刻: {3, 4, 5}
仮想文字列: "BBBWWW...."

segment 木では、各文字に次の値を入れる。

B: {1, 0, 0}
W: {0, 1, 0}
.: {0, 0, 0}

全体では「Bの個数、Wの個数、W→Bの組数」を管理する。
初期状態では W より後ろに B がないので、全体の情報は {3, 3, 0} となる。

最初のクエリ 1 0 では、$0$ 行目を黒く塗る。
位置 $0$ を . に戻し、位置 $6$ に B を入れる。

行の最終時刻: {6, 1, 2}
列の最終時刻: {3, 4, 5}
仮想文字列: ".BBWWWB..."
segment木全体: {3, 3, 3}

W→B の組数は $3$ なので、黒マス数は $3$ となる。

次のクエリ 1 2 では、位置 $2$ を . に戻し、位置 $7$ に B を入れる。

行の最終時刻: {6, 1, 7}
列の最終時刻: {3, 4, 5}
仮想文字列: ".B.WWWBB.."
segment木全体: {3, 3, 6}

W→B の組数は $6$ なので、黒マス数は $6$ となる。

次のクエリ 2 1 では、位置 $4$ を . に戻し、位置 $8$ に W を入れる。

行の最終時刻: {6, 1, 7}
列の最終時刻: {3, 8, 5}
仮想文字列: ".B.W.WBBW."
segment木全体: {3, 3, 4}

W→B の組数は $4$ なので、黒マス数は $4$ となる。

最後のクエリ 1 0 では、位置 $6$ を . に戻し、位置 $9$ に B を入れる。

行の最終時刻: {9, 1, 7}
列の最終時刻: {3, 8, 5}
仮想文字列: ".B.W.W.BWB"
segment木全体: {3, 3, 5}

W→B の組数は $5$ なので、黒マス数は $5$ となる。

したがって、各クエリ後の答えは順に $3,6,4,5$ となる。

注意点

黒く塗られているマスの個数は、int 型からはみ出る。
W→Bの組数の管理は long long 型を用いること。

別解

特になし。