P3113 [USACO14DEC] Marathon G

贝茜自己是一名狂热的马拉松跑者，她喜欢为她的牛朋友们设计马拉松路线。最近，她设计了一条由 $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 翻译）