P3113 [USACO14DEC] Marathon G

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

贝茜自己是一名狂热的马拉松跑者，她喜欢为她的牛朋友们设计马拉松路线。最近，她设计了一条由 $N$ 个检查点组成的路线，这些检查点必须按顺序访问。 不幸的是，贝茜意识到其他牛可能没有足够的耐力跑完整条路线。因此，她想知道某些子路线需要多长时间，其中子路线是完整路线中连续的一段。更复杂的是，贝茜知道其他牛可能会因为懒惰而选择在跑子路线时跳过一个检查点——无论哪个检查点能使总旅行时间最短。然而，他们不允许跳过子路线的第一个或最后一个检查点。 为了构建最佳的马拉松路线，贝茜想研究对当前路线中的检查点位置进行更改的影响。请帮助她确定对检查点位置的某些更改将如何影响跑不同子路线所需的时间（考虑到牛可能会在跑子路线时选择省略一个检查点）。 由于路线设置在市中心的街道网格中，位于 $(x_1,y_1)$ 和 $(x_2,y_2)$ 的两个检查点之间的距离由 $\lvert x_1-x_2\rvert+\lvert y_1-y_2\rvert$ 给出。

第一行给出 $N$ 和 $Q$。 接下来的 $N$ 行包含 $N$ 个检查点的 $(x,y)$ 位置，按照路线中必须访问的顺序给出。所有坐标的范围为 $-1000$ 到 $1000$。 接下来的 $Q$ 行由更新和查询组成，每行一个操作，按给定顺序处理。这些行的形式要么是 `U I X Y`，要么是 `Q I J`。 形式为 `U I X Y` 的行表示检查点 $I$ 的位置要更改为 $(X,Y)$。 形式为 `Q I J` 的行要求输出从检查点 $I$ 到检查点 $J$ 的子路线的最短旅行时间，前提是牛选择在此子路线中跳过一个检查点（但不能是端点 $I$ 和 $J$）。

对于每个子路线长度请求，在单独一行输出所需的长度。

对于 $100\%$ 的数据，$1\le N, Q\le10^5,1\le I\le N$。 （本题由 ChatGPT 4o 翻译）