考察
各windowの外側に残るdistinct数は、値xごとに『grid全体の出現数−window内出現数が正か』を数えればよい。
H,W,N≤300なので、値ごとに2D prefix countを持つHWN規模の集計が制約内に収まる。
採用する候補: 各値xのindicator gridに2D累積和を作り、各h×w window内のx個数を全体個数から引いて外に残る値を数える。
棄却する候補: 各windowごとにblackout外の全HW cellを走査し、setでdistinctを数える。
window数もHW規模で、全体が(HW)²になり得る。
count[r][c][x]を(1,1)…(r,c)のx出現数として全値分構築する。各top-left(k,l)とxについてh×w内個数を4項で取り、total[x]との差が正ならanswerを1増やして表形式で出力する。
典型の発動条件
値別2D累積和
発動条件: 小さい値域の各カテゴリについて、多数のrectangle内出現数queryが必要なとき。
カテゴリindicatorのprefix countを第三次元に持ち、4 corner差を取る。
補集合でdistinct判定
発動条件: 領域外のdistinct種類数を求め、全体頻度と領域内頻度が得られるとき。
total-inside>0のカテゴリ数を数える。
問題固有の要素
blackout外を直接見る代わりに、各値がblackout内へ全出現を奪われたかだけを判定すればよい。
別の問題へ持ち帰る視点: 領域削除後のdistinct数は、カテゴリごとの全体頻度と削除領域頻度の一致判定へ分解する。
正当性
値xが答えに含まれる条件はtotal[x]>insideWindow[x]であり、window外の位置を個別に列挙する必要はない。 rectangle内個数は4 cornerの2D prefix差で求まり、同じprefix tableを全windowで再利用できる。 windowごとのcell再走査を避け、各値のrectangle countを定数時間で得られる。
実装上の注意
- prefix配列の0行・0列を用意し、window端点のinclusive/exclusive規約を統一する。
- 実際に出現しない値はtotal=0なので答えへ加えず、Nの全値を走査しても条件をstrictly positiveにする。
復習の核
- ある値の全出現がwindow内に入る場合と1個だけ外へ残る場合を描き、判定がtotal==insideかどうかに集約されることを確認する。
計算量と制約
時間
O(HWN+(H−h+1)(W−w+1)N)、Nは色数、h×wを切り抜く。
空間
O(HWN)、色別2D prefix。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq H,W,N \leq 300; 1 \leq h \leq H; 1 \leq w \leq W; (h,w)\neq(H,W); 1 \leq A _ {i,j} \leq N\ (1\leq i\leq H,1\leq j\leq W); All values in the input are integers.
出典