A619.[USACO 2014 December Gold]马拉松

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 <= N <= 100,000) that must be
visited in sequence.

Unfortunately, Bessie realizes that the other cows may not have the
stamina to run the full route. She therefore wants to know how long
certain sub-routes take to run, where a sub-route is a contiguous
subsequence of the checkpoints from the full route. To make matters
more complicated, Bessie knows that the other cows, being lazy, might
choose to skip one checkpoint any time they run a sub-route --
whichever one results in a minimum total travel time. They are not
allowed to skip the first or last checkpoints in a sub-route, however.

In order to build the best possible marathon course, Bessie wants to
investigate the ramifications of making changes to the checkpoint
locations in her current course. Please help her determine how
certain changes to checkpoint locations will affect the time required
to run different sub-routes (taking into account that the cows might
choose to omit one checkpoint any time they run a sub-route).

Since the course is set in a downtown area with a grid of streets, the
distance between two checkpoints at locations (x1, y1) and (x2, y2) is
given by |x1-x2| + |y1-y2|.

INPUT:
The first line gives N and Q (1 <= Q <= 100,000).

The next N lines contain (x, y) locations of N checkpoints in the
sequence they must be visited along the route. All coordinates
are in the range -1000 .. 1000.

The next Q lines consist of updates and queries, one per line, to be
processed in the order they are given. Lines will either take the form
"U I X Y" or "Q I J". A line of the form "U I X Y" indicates that the
location of checkpoint I (1 <= I <= N) is to be changed to location
(X, Y). A line of the form "Q I J" asks for the minimum travel time
of the sub-route from checkpoint I to checkpoint J (I <= J), given
that the cows choose to skip one checkpoint along this sub-route (but
not the endpoints I and J).

OUTPUT:
For each sub-route length request, output on a single line the desired
length.

作为一名狂热的马拉松运动员，贝茜喜欢为她的奶牛同伴开设马拉松课程。最近她设计了一个有 $N$ 个检查点的路线，要按顺序访问。

不幸的是，贝茜意识到其他的奶牛可能没有耐力跑完全程。因此，她想知道特定的子路线多久能跑完，其中子路线是指从完整路线中的检查点中截取的连续子序列。更复杂的是，贝西知道她的牛十分懒惰，可能会在跑子路线时选择跳过一个检查点，无论哪一种方法都能在最短的时间内完成。但是她们不允许跳过子路线中的第一个或最后一个检查点。

为了建立尽可能最好的马拉松赛道，贝茜想要研究一下在她目前的课程中对检查点位置做出改变后可能造成的后果。请帮助她确定检查点位置的哪些更改将会影响运行不同子路线所需的时间(考虑到奶牛可能会选择在子路线跑步时忽略一个检查点)。

比赛设置在市中心一个有街道网格上， 两个检查点之间的距离由$(x1,y1)$ 和 $(x2,y2)$ 得出，为$| x1 - x2 | + | y1 - y2 |$。

第一行给出了 $N$ 和 $Q$（$1 \le Q \le 10 ^5$）。

接下来的 $N$ 行每行一个检查点 ( $x$ , $y$ ) 的位置，他们必须沿着这些检查点的顺序跑，坐标范围在$-1 \times 10^3$~

$1 \times 10^3$。

下面 $Q$ 行由更新和查询组成，每行一个，按照它们给出的顺序进行处理。可以采取“$U$ $I$ $X$ $Y$”或“$Q$ $I$ $J$”的形式。

“$U$ $I$ $X$ $Y$” 形式的一行表示检查点 $I$（$1 \le I \le N$）的位置将被更改为位置$(X, Y)$.

“$Q$ $I$ $J$” 形式一行要求出从检查点 $I$ 到检查点 $J$ ($I \le J$)的子路线的最短距离，假设奶牛选择跳过这条子路线上的一个检查点(但不跳过终点 $I$ 和 $J$ )。

对于每个请求，输出 $I$ 到 $J$ 的最短距离。