DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

砲

問題に戻る

解説

一列内の条件 ある行に ttt 個の駒があり、最左・最右の駒の列を L,RL,RL,R とする。

  • t≤1t\leq1t≤1 なら横方向では取れない。
  • t=2t=2t=2 なら LLL より左または RRR より右の空きマスでのみ取れる。二つの駒の間ではどちらの方向にも二つの駒がない。
  • t≥3t\geq3t≥3 ならすべての空きマスで取れる。左右の少なくとも一方に二つ以上の駒があるからである。

列にも同じ条件が成り立つ。各行・列で駒数と最初・最後の位置だけを保存すればよい。

横方向を先に数える 各行で横方向に取れるマスを先に加算する。t=2t=2t=2 なら (L−1)+(M−R)(L-1)+(M-R)(L−1)+(M−R) 個、t≥3t\geq3t なら 個である。まだ数えていない次の空き区間だけで縦方向を確認する。

  • t=0t=0t=0: [1,M][1,M][1,M]。
  • t=1t=1t=1: [1,L−1][1,L-1][1, と 。

左端が右端を超える空区間は無視する。どの区間にも駒は存在しない。

行の走査と Fenwick 木 現在行で縦方向に取れる列を 111、それ以外を 000 として Fenwick 木に保存する。駒が一つ以下の列は常に 000、三つ以上の列は常に 111 である。ちょうど二つの駒が U,DU,DU,D 行にある列は、UUU より上または より下でのみ となる。

二駒の列を初めは 111 とし、UUU 行の処理前に 000、D+1D+1D+1 行の処理前に 111 に変更する。D=ND=ND なら後者は不要である。三駒以上の列では駒の位置も になるが、照会区間には駒が含まれないため問題ない。

イベントを行番号で整列し、上から順に処理する。各行のイベントを先に適用し、残りの最大二区間の和を答えに加える。横または縦に取れる空きマスがちょうど一度ずつ数えられる。

計算量と数値範囲 イベント数は KKK 以下である。時間計算量は O(N+M+Klog⁡(K+1)+Klog⁡(M+1)+Nlog⁡(M+1))O(N+M+K\log(K+1)+K\log(M+1)+N\log(M+1))O(N+M+Klog(K+1)、空間計算量は 。 なので、答えと盤面面積の積は符号付き ビット整数で計算する。各列の数、木の区間和、添字は 以下である。生成器のマス番号も 未満であり ビットに収まる。

サブタスク 1 は全マスを走査し行と列の条件を直接確認する。時間・空間は O(NM+N+M+K)O(NM+N+M+K)O(NM+N+M+K) で、NM≤10 000NM\leq10\,000NM≤10000 なら十分である。サブタスク 2 は上記の走査を使う。

Solution written by GPT6

≥
3
M−tM-tM−t
L
−
1]
[L+1,M][L+1,M][L+1,M]
  • t=2t=2t=2: [L+1,R−1][L+1,R-1][L+1,R−1]。
  • t≥3t\geq3t≥3: 残りの区間はない。
  • DDD
    111
    =
    N
    111
    +
    Klog(M+
    1)+
    Nlog(M+
    1))
    O(N+M+K)O(N+M+K)O(N+M+K)
    0≤answer≤NM−K<2.5⋅10110\leq\mathrm{answer}\leq NM-K<2.5\cdot10^{11}0≤answer≤NM−K<2.5⋅1011
    646464
    500 000500\,000500000
    NMNMNM
    646464