ABC 401-500/ABC449F - Grid Clipping - 競技プログラミング用 知識集積所

---

問題

ABC449F

必要知識

B以下レベルの内容は省略

• 特になし

考え方

左上のマスとして選べるマス数を考えればよい。
そのためには、まず黒が含まれてもいいから枠内に収まる位置取りの個数を出しておき、そこから黒を含んでしまう分を取り除けばよい。

これは、発想として、上から順に一段ずつ見て、「この黒のせいで、この段のここからここまでダメ」という範囲をmultiset※で管理し、区間長合計を引くことを繰り返せばよい。
（これでもまだTLEするが、そこはあとで改善する）
具体的には、黒のh段上に来た時にダメになる範囲を追加して、黒の段の下に来た時にそれを取り除けばよい。
仮にmultiset※に区間Bを追加したときにA-B-Cの順になったとすると、ダメな長さは

• Bの長さを足す
• AとBが重複する長さを引く
• BとCが重複する長さを引く
• AとCが重複する長さを足す

の4つの計算をすることで更新できる。
これは、問題の都合上multiset※内で範囲の左端も右端も同時に単調非減少な順に並んでくれるから可能なことである。
同様に、multiset※から区間を削除するときは足すか引くかを全部逆にすればよい。
これで、1行1行はO(logN)で処理できるようになった。

これでも本当に1行ずつ処理すると盤面サイズの縦幅が大きすぎてTLEする。
しかし、範囲の追加クエリや削除クエリが来ない範囲は複数段まとめて掛け算で計算できるため、それを採用すればO(NlogN)で終わらせることができる。

解答例

解答例

注意点

long long型を使う。

盤面サイズは非常に大きくなる。

別解