P3113 [USACO14DEC] Marathon G

作为一名狂热的马拉松长跑运动员，贝茜喜欢为她的同伴们开设马拉松课程。她最近设计了一个有N个检查点的路线(1 < = N < = 100,000)，必须按顺序经过。 不幸的是，贝茜意识到其他的奶牛可能没有足够的耐力跑完全程。因此，她想知道特定的子路线需要多长时间才能跑完，其中的子路线是从完整路线的检查点中截取的的连续子序列。让事情变得更复杂的是，贝西知道其他的牛十分懒惰，可能会选择在任何时候跳过一个检查点——无论哪一种方法都能在最短的时间内完成。然而，他们不允许在子路线中跳过第一个或最后一个检查点。 为了建造最好的马拉松赛道，贝茜想要研究一下在她目前的课程中对检查点位置做出改变后可能造成的后果。请帮助她确定检查点位置的哪些更改将会影响运行不同子路线所需的时间(考虑到奶牛可能会选择在子路线跑步时忽略一个检查点)。 由于该课程设置在市中心的街道网络中，两个检查点之间的距离(x1,y1)和(x2,y2)是由| x1 - x2 | + | y1 - y2 |得出的。

An avid marathon runner herself, Bessie enjoys creating marathon courses for her fellow cows to run. She has most recently designed a route specified by N checkpoints (1

无

无