コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 2350 (記事作成時点)

供養

解法

簡単のため多角形がすべて長方形の場合を考えると、長方形が $(x_{i, 1}, y_{i, 1}), (x_{i, 1}, y_{i, 2}), (x_{i, 2}, y_{i, 1}), (x_{i, 2}, y_{i, 2})$ の4点からなるとき、$(x_{j}, y_{j})$ がいくつの長方形に含まれるかという問題になる
- $x_{i, 1} \lt x_{i, 2}, y_{i, 1} \lt y_{i, 2}$ とする
2次元区間和を使って $x = 0, 1, \dots$ のときに $y = 0, 1, \dots$ にいくつの長方形が重なっているかを区間和を更新しながら求める
- $x = x_{i, 1}$ のときに $y = y_{i, 1}$ で $+1$、$y = y_{i, 2}$ で $-1$
- $x = x_{i, 2}$ のときに $y = y_{i, 1}$ で $-1$、$y = y_{i, 2}$ で $+1$
- $x = x_{j}$ のときに、その時点まで操作をした後の $\lbrack 0, y_{j} \rbrack$ の区間和がクエリの答えとなる
- 区間和はBITで持っておくと任意の $y$ についての計算ができる
多角形が長方形でない場合の処理を考える
- 多角形を $x$ 軸に平行にスライスすると長方形の集合となる
- このとき、各長方形の操作を合算すると元の多角形で頂点ではない部分の操作は打ち消しあう
  - $(x, y)$ が左下（右下）の場合の操作と左上（右上）の場合の操作が打ち消しあう関係にある
- 残った操作は長方形の左下もしくは右上に相当する操作と左上もしくは右下に相当する操作が元の多角形の頂点順に交互に現れる
- $x$ について最小な頂点集合の中で $y$ について最小な頂点 $(x_{i, j}, y_{i, j})$ は必ず長方形の左下に相当する
- $(x_{i, j}, y_{i, j})$ から順にどちらの操作かを決めていき、対応する位置での操作となるよう操作列に組み込んでいけばよい