Codeforces Round #501 (Div. 3)E2. Stars Drawing (Hard Edition)
問題概要
書くのだるいので, サイトの文章を読んでください....
制約
解法
こういうのと全く一緒です.
まず, 星の数は最小化する必要がなく, また重なってもいいということから, 作れる星は全部作ってしまうのがよいです(作れるのに作らないことは '*' を埋められるのに埋めないことになり, 明らかに無駄です).
そこで, あるマスについて, 自分の上下左右に何個 '*' があるかを数えたい気分になります. 普通に実装すると で TLE します.
そこで, を自分の左にある '*' の数として定義します. これは, 動的に更新すれば
で構築できます(累積和みたいな感じです). あとは 右上下も同様に前計算すれば, あるマスの 上下左右の '*' の数は
で求められることになります.
あとはつくれるだけ星を作り, それがもとの分布と一致しているかを確かめれば良いです. ある区間を '*' に変更するクエリは愚直にやると になるので, うまいことやってください. imos 法が楽だとは思いますが, 遅延セグ木, dsu なんかでもできると思います.
実装
長いですが, やってることは非常にシンプルです.
