切比雪夫距離

[maxlimits_{i=1}^{n} |ax_i-ay_i|
]

就是坐標(biāo)差的絕對值的極值

然后我們思考曼哈頓距離和切比雪夫距離的關(guān)系：

在紙上建一個二維坐標(biāo)系，然后畫一個與原點(diǎn)曼哈頓距離為 (5) 的正方形 (S_1)

然后再畫一個切比雪夫距離為 (5) 的正方形 (S_2)

看看它們，是不是有某種奇妙的聯(lián)系：(S_1) 旋轉(zhuǎn) (45) 度后放大為原來原來的兩倍就是 (S_2)

互相轉(zhuǎn)化的公式為$(x,y) on S_1 ightarrow(frac{x+y}{2},frac{x-y}{2}) on S_2 $

這里可以用來使某些題的處理更加方便

例題

Luogu5193 [TJOI2012]炸彈

曼哈頓兩個維度有點(diǎn)頭疼，不好處理，那我們轉(zhuǎn)切比雪夫

這樣我們把距離轉(zhuǎn)成了以每個點(diǎn)為原點(diǎn)，在定邊長切比雪夫距離矩形中框點(diǎn)

我們上 (map) 掃描線就行了

我們在處理每個點(diǎn)的時候就直接找那個離他 (y) 最近的上下兩個就行了

因?yàn)槟莻€點(diǎn)已經(jīng)考慮了前面的點(diǎn)

Luogu3966 單詞

看出來是個切比雪夫不難

然后把切比雪夫轉(zhuǎn)成曼哈頓

這樣距離就可以前綴和求啦！

BZOJ2735世博會

把發(fā)現(xiàn)題目里面要求的是一個切比雪夫距離

那么轉(zhuǎn)到曼哈頓上維護(hù)中位數(shù)和前后綴和即可

然后寫一下這題目我犯的所有錯誤：

1.線段樹查詢：

if(st<=mid) ...
else ...->if(ed>mid)

2.求和的時候減東西減錯了，應(yīng)該拿 (pair o second) 來

然后就沒了

總結(jié)

以上是生活随笔為你收集整理的「学习笔记」切比雪夫距离的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。