2020年5月28日木曜日

JOI2010 春合宿 - Sengoku

(i,j)(i, j)を通る傾き11の直線の切片はjij-iで、傾き1-1の直線の切片はi+ji+jになる。

とりあえず重複のことは忘れて番兵毎に数えると、傾き11の直線の通るマスはLijL - |i-j|個あり、傾き1-1の直線の通るマスはi+j<Li+j < Lのときi+j+1i+j+1個、i+jLi+j \ge Lのとき2L(i+j+1)2L - (i+j+1)個あることがわかるので、まずはこれらの総和が基本になる。

次に、重複を除くことを考える。まず、切片と傾きが同じ直線は完全に重なるので、登場した切片を記録しておいて、前に見たものは無視することで重複を避けられる。

最後に傾き11の直線と傾き1-1の直線の交点の数を引く必要がある。まず、交点が格子点になるのは切片が偶数同士、奇数同士の場合なので、切片が偶数の直線についてのみ考えることにする。(奇数のものの交点も同様に数えられる。) 傾き11で切片がCCの直線と傾き1-1の直線が与えられた領域内で交わるのは、後者の切片が[C,2(L1)C[|C|, 2(L-1) - |C|]に入っているとき、またその時に限るので、ソートしておいてそれぞれ二分探索で数えられる。