AT_abc437_f [ABC437F] Manhattan Christmas Tree 2

在一个二维平面上有 $N$ 棵圣诞树。第 $i$ 棵 $(1 \leq i \leq N)$ 圣诞树的位置为坐标 $(X_i, Y_i)$。 你会得到 $Q$ 个询问。请依次处理这些询问。每个询问有以下两种类型之一： - 类型 $1$：格式为 `1 i x y`。将第 $i$ 棵圣诞树的位置更改为 $(x, y)$。 - 类型 $2$：格式为 `2 L R x y`。输出坐标 $(x, y)$ 到第 $L,L+1,\ldots,R$ 棵圣诞树中距离最远的那棵的曼哈顿距离。 其中，坐标 $(x_1, y_1)$ 与坐标 $(x_2, y_2)$ 的曼哈顿距离定义为 $|x_1-x_2|+|y_1-y_2|$。

输入按如下格式从标准输入给出： > $N$ $Q$ > $X_1$ $Y_1$ > $X_2$ $Y_2$ > ⋮ > $X_N$ $Y_N$ > $\text{query}_1$ > $\text{query}_2$ > ⋮ > $\text{query}_Q$ 第 $i$ 个询问 $\text{query}_i$ 具有如下两种格式之一： > $1$ $i$ $x$ $y$ > $2$ $L$ $R$ $x$ $y$

根据问题描述的要求，输出每个类型 $2$ 的询问的答案，并用换行分隔。

### 样例解释 1 初始时，第 $1$、$2$、$3$ 棵圣诞树分别位于坐标 $(-1,-1)$、$(1,2)$、$(-2,1)$。 各个询问的处理如下： - 对于第一个询问，坐标 $(0,0)$ 到第 $1$ 和 $2$ 棵树的曼哈顿距离分别为 $2$ 和 $3$，最大值为 $3$，因此输出 $3$。 - 对于第二个询问，坐标 $(-1,2)$ 到第 $1$、$2$、$3$ 棵树的曼哈顿距离分别为 $3$、$2$、$2$，最大值为 $3$，因此输出 $3$。 - 第三个询问将第 $1$ 棵树的坐标更改为 $(0,1)$。此时 $1$、$2$、$3$ 棵树的坐标依次为 $(0,1)$、$(1,2)$、$(-2,1)$。 - 对于第四个询问，坐标 $(-1,2)$ 到第 $1$、$2$、$3$ 棵树的曼哈顿距离分别为 $2$、$2$、$2$，最大值为 $2$，因此输出 $2$。 ### 数据范围 - $1 \leq N, Q \leq 2 \times 10^5$ - $-10^9 \leq X_i, Y_i \leq 10^9$ - $1 \leq i \leq N$ - $1 \leq L \leq R \leq N$ - $-10^9 \leq x, y \leq 10^9$ - 所有输入值均为整数。 由 ChatGPT 5 翻译