一列内の条件 ある行に 個の駒があり、最左・最右の駒の列を とする。
列にも同じ条件が成り立つ。各行・列で駒数と最初・最後の位置だけを保存すればよい。
横方向を先に数える 各行で横方向に取れるマスを先に加算する。 なら 個、 なら 個である。まだ数えていない次の空き区間だけで縦方向を確認する。
左端が右端を超える空区間は無視する。どの区間にも駒は存在しない。
行の走査と Fenwick 木 現在行で縦方向に取れる列を 、それ以外を として Fenwick 木に保存する。駒が一つ以下の列は常に 、三つ以上の列は常に である。ちょうど二つの駒が 行にある列は、 より上または より下でのみ となる。
二駒の列を初めは とし、 行の処理前に 、 行の処理前に に変更する。 なら後者は不要である。三駒以上の列では駒の位置も になるが、照会区間には駒が含まれないため問題ない。
イベントを行番号で整列し、上から順に処理する。各行のイベントを先に適用し、残りの最大二区間の和を答えに加える。横または縦に取れる空きマスがちょうど一度ずつ数えられる。
計算量と数値範囲 イベント数は 以下である。時間計算量は 、空間計算量は 。 なので、答えと盤面面積の積は符号付き ビット整数で計算する。各列の数、木の区間和、添字は 以下である。生成器のマス番号も 未満であり ビットに収まる。
サブタスク 1 は全マスを走査し行と列の条件を直接確認する。時間・空間は で、 なら十分である。サブタスク 2 は上記の走査を使う。
Solution written by GPT6