分数: 500 点
问题陈述
有 N 二维平面上的圣诞树。的 i-th (1\le i\le 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|.
约束
- 1\le N,Q\le 2\times 10^5
- -10^9\le X_i,Y_i\le 10^9
- 1\le i\le N
- 1\le L\le R\le N
- -10^9\le x,y\le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N Q
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
在这里, i第一个查询 \text{query}_i 采用以下格式之一给出:
1 i x y
2 L R x y
输出
根据问题陈述中的说明输出查询的答案,以换行符分隔。
样本输入 1
3 4 -1 -1 1 2 -2 1 2 1 2 0 0 2 1 3 -1 2 1 1 0 1 2 1 3 -1 2
示例输出 1
3 3 2
最初, 1圣, 2nd, 3rd 圣诞树位于坐标处 (-1,-1), (1,2), (-2,1)。
每个查询的处理方式如下:
- 曼哈顿距 1圣和 2nd 圣诞树坐标 分别是 (0,0) 是 2 和 3。因此,输出 3,这是其中的最大值 2,3.
- 曼哈顿距 1圣, 2nd, 3rd 圣诞树坐标 (-1,2) 是 3, 2, 2。因此,输出 3,这是其中的最大值 3,2,2.
- 更改坐标 1st 圣诞树到 (0,1)。的坐标 1圣, 2nd, 3rd圣诞树成为 (0,1),(1,2),(-2,1)。
- 曼哈顿距 1圣, 2nd, 3rd 圣诞树坐标 (-1,2) 是 2, 2, 2。因此,输出 2,这是其中的最大值 2,2,2.
示例输入 2
5 7 -9 5 -2 -9 10 -6 9 8 2 9 1 3 -9 -6 2 3 4 2 7 1 4 -2 -10 2 1 2 0 -10 2 3 4 10 -9 2 3 4 8 7 2 5 5 0 2
示例输出 2
24 24 22 30 9