ABC461E - E-liter

解法

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

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

$i$ 番目のクエリがタイプ $1$ で、かつその行を最後に塗った場合、$i$ 文字目を 'B' とする
$i$ 番目のクエリがタイプ $2$ で、かつその列を最後に塗った場合、$i$ 文字目を 'W' とする
$i$ 番目のクエリが上記のどちらでもない場合、$i$ 文字目を '.' とする

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

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

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

入力例1での動作

盤面サイズとクエリ数を受け取る。

n: 3
q: 4

サイズ $2N+Q = 10$ のsegment木を用意する。
中身は「Bの個数、Wの個数、W→Bの組数」。

time: 0
仮想文字列: ".........."

0	1	2	3	4	5	6	7	8	9	e	e	e	e	e	e
{0,0,0}
{0,0,0}								{0,0,0}
{0,0,0}				{0,0,0}				{0,0,0}				e
{0,0,0}		{0,0,0}		{0,0,0}		{0,0,0}		{0,0,0}		e		e		e
{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	e	e	e	e	e	e

全ての行を $1$ 回ずつ塗る。
行タイムスタンプとsegment木を更新。

time: 3
r_stamp: {0, 1, 2}
仮想文字列: "BBB......."

0	1	2	3	4	5	6	7	8	9	e	e	e	e	e	e
{3,0,0}
{3,0,0}								{0,0,0}
{3,0,0}				{0,0,0}				{0,0,0}				e
{2,0,0}		{1,0,0}		{0,0,0}		{0,0,0}		{0,0,0}		e		e		e
{1,0,0}	{1,0,0}	{1,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	e	e	e	e	e	e

全ての列を $1$ 回ずつ塗る。
列タイムスタンプとsegment木を更新。

time: 6
r_stamp: {0, 1, 2}
c_stamp: {3, 4, 5}
仮想文字列: "BBBWWW...."

0	1	2	3	4	5	6	7	8	9	e	e	e	e	e	e
{3,3,0}
{3,3,0}								{0,0,0}
{3,1,0}				{0,2,0}				{0,0,0}				e
{2,0,0}		{1,1,0}		{0,2,0}		{0,0,0}		{0,0,0}		e		e		e
{1,0,0}	{1,0,0}	{1,0,0}	{0,1,0}	{0,1,0}	{0,1,0}	{0,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	e	e	e	e	e	e

クエリ 1 1 を受け取る。
行タイムスタンプとsegment木を更新。
all_prod() のW→Bの組数である 3 が答え。

time: 7
r_stamp: {6, 1, 2}
c_stamp: {3, 4, 5}
仮想文字列: ".BBWWWB..."

0	1	2	3	4	5	6	7	8	9	e	e	e	e	e	e
{3,3,3}
{3,3,3}								{0,0,0}
{2,1,0}				{1,2,2}				{0,0,0}				e
{1,0,0}		{1,1,0}		{0,2,0}		{1,0,0}		{0,0,0}		e		e		e
{0,0,0}	{1,0,0}	{1,0,0}	{0,1,0}	{0,1,0}	{0,1,0}	{1,0,0}	{0,0,0}	{0,0,0}	{0,0,0}	e	e	e	e	e	e

クエリ 1 3 を受け取る。
行タイムスタンプとsegment木を更新。
all_prod() のW→Bの組数である 6 が答え。

time: 8
r_stamp: {6, 1, 7}
c_stamp: {3, 4, 5}
仮想文字列: ".B.WWWBB.."

0	1	2	3	4	5	6	7	8	9	e	e	e	e	e	e
{3,3,6}
{3,3,6}								{0,0,0}
{1,1,0}				{2,2,4}				{0,0,0}				e
{1,0,0}		{0,1,0}		{0,2,0}		{2,0,0}		{0,0,0}		e		e		e
{0,0,0}	{1,0,0}	{0,0,0}	{0,1,0}	{0,1,0}	{0,1,0}	{1,0,0}	{1,0,0}	{0,0,0}	{0,0,0}	e	e	e	e	e	e

クエリ 2 2 を受け取る。
列タイムスタンプとsegment木を更新。
all_prod() のW→Bの組数である 4 が答え。

time: 9
r_stamp: {6, 1, 7}
c_stamp: {3, 8, 5}
仮想文字列: ".B.W.WBBW."

0	1	2	3	4	5	6	7	8	9	e	e	e	e	e	e
{3,3,4}
{2,3,4}								{0,1,0}
{1,1,0}				{2,1,2}				{0,1,0}				e
{1,0,0}		{0,1,0}		{0,1,0}		{2,0,0}		{0,1,0}		e		e		e
{0,0,0}	{1,0,0}	{0,0,0}	{0,1,0}	{0,0,0}	{0,1,0}	{1,0,0}	{1,0,0}	{0,1,0}	{0,0,0}	e	e	e	e	e	e

クエリ 1 1 を受け取る。
行タイムスタンプとsegment木を更新。
all_prod() のW→Bの組数である 5 が答え。

time: 10
r_stamp: {9, 1, 7}
c_stamp: {3, 8, 5}
仮想文字列: ".B.W.W.BWB"

0	1	2	3	4	5	6	7	8	9	e	e	e	e	e	e
{3,3,5}
{2,2,2}								{1,1,1}
{1,1,0}				{1,1,1}				{1,1,1}				e
{1,0,0}		{0,1,0}		{0,1,0}		{1,0,0}		{1,1,1}		e		e		e
{0,0,0}	{1,0,0}	{0,0,0}	{0,1,0}	{0,0,0}	{0,1,0}	{0,0,0}	{1,0,0}	{0,1,0}	{1,0,0}	e	e	e	e	e	e

注意点

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

別解

特になし。