競技プログラミング用 知識集積所
ABC437F - Manhattan Christmas Tree 2
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
考え方
マンハッタン距離は、そのまま扱ってもよいが、45度座標回転※して√2倍に拡大すると、チェビシェフ距離になるので扱いやすくなる。
つまり、(x,y)を(x-y,x+y)に変換すると扱いやすい。
つまり、(x,y)を(x-y,x+y)に変換すると扱いやすい。
その上で、L番からR番までで最も遠いチェビシェフ距離を考えるには、それらのツリーの座標の上下左右の最大値や最小値を求めることになる。
これはsegment木※に範囲データを載せる（または、方向ごとに4つsegment木※を用意する）ことで更新と取得の両立が可能。
あとは実装力勝負。
これはsegment木※に範囲データを載せる（または、方向ごとに4つsegment木※を用意する）ことで更新と取得の両立が可能。
あとは実装力勝負。
解答例
注意点
答えにはlong long型を用いる
マイナス側も10^9までありえる関係で、答えが最大4*10^9になる。
long long型にすること。（unsigned intでもよい）
long long型にすること。（unsigned intでもよい）
