← 返回题目列表

AtCoder · abc437_f

I. 曼哈顿圣诞树2

中文机器翻译题面 查看原题

分数: 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