ABC 401-500/ABC432D - Suddenly, A Tempest - 競技プログラミング用 知識集積所

---

問題

ABC432D

必要知識

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

• UnionFind木※

考え方

問題で言っていることは何も難しくなく、実装力勝負。

前半は、全ての大嵐が通過した後の状態を求める問題。
長方形領域を4つのパラメータ（例えば上下左右のライン位置[l,r)と[d,u)とか）で持ち、大嵐が来るたびに

• Xの場合
  • 全体が上にズレる
  • 全体が下にズレる
  • 裂けて2つの長方形領域にわかれる
• Yの場合
  • 全体が左にズレる
  • 全体が右にズレる
  • 裂けて2つの長方形領域にわかれる

の6パターンのどれに該当するかで長方形領域の一覧を更新していけばいい。

後半は、それらが連結かどうかを考える問題。
これはUnionFind木※を使えばよい。
2つの長方形の組み合わせについて、

• 上下の位置関係だけ見たら接しているように見え、左右の位置関係だけ見たら重なっているように見える
• 左右の位置関係だけ見たら接しているように見え、上下の位置関係だけ見たら重なっているように見える

のいずれかであれば、これらの長方形は実は隣り合っている。
隣り合っている長方形の番号同士をUnionFind木※上で連結し、全部終わったら連結成分ごとに面積を足していけばよい。

問題は計算量だが、仮に大嵐で最大効率で多く分割されまくったとして、大嵐1回で領域2つ、2回で4つ、3回で6つ、4回で10個？と考えると、14回でも10000は超えそうにない。
（公式解説によると、実際の最大は471らしい）
なので、領域から2つを選ぶループは計算量的に余裕をもって間に合うだろうと判断される。

最後に昇順に並べるのを忘れないこと。

解答例

解答例

注意点

long long型を用いること

入力例にもあるが、答えはint型の上限を超えることがある。
領域の座標も同じく。

別解