题目详情题解（0）讨论（0）提交记录（0）

AT_abc437_f.[ABC437F] Manhattan Christmas Tree 2

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

在一个二维平面上有 NN 棵圣诞树。第 ii 棵 (1≤i≤N)(1 \leq i \leq N) 圣诞树的位置为坐标 (Xi,Yi)(X_i, Y_i)。

你会得到 QQ 个询问。请依次处理这些询问。每个询问有以下两种类型之一：

  • 类型 11：格式为 1 i x y。将第 ii 棵圣诞树的位置更改为 (x,y)(x, y)。
  • 类型 22：格式为 2 L R x y。输出坐标 (x,y)(x, y) 到第 L,L+1,…,RL,L+1,\ldots,R 棵圣诞树中距离最远的那棵的曼哈顿距离。

其中，坐标 (x1,y1)(x_1, y_1) 与坐标 (x2,y2)(x_2, y_2) 的曼哈顿距离定义为 ∣x1−x2∣+∣y1−y2∣|x_1-x_2|+|y_1-y_2|。

输入格式

输入按如下格式从标准输入给出：

NN QQ
X1X_1 Y1Y_1
X2X_2 Y2Y_2
⋮
XNX_N YNY_N
query1\text{query}_1
query2\text{query}_2
⋮
queryQ\text{query}_Q

第 ii 个询问 queryi\text{query}_i 具有如下两种格式之一：

11 ii xx yy

22 LL RR xx yy

输出格式

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

输入输出样例

  • 输入#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

  • 输入#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

说明/提示

样例解释 1

初始时，第 11、22、33 棵圣诞树分别位于坐标 (−1,−1)(-1,-1)、(1,2)(1,2)、(−2,1)(-2,1)。

各个询问的处理如下：

  • 对于第一个询问，坐标 (0,0)(0,0) 到第 11 和 22 棵树的曼哈顿距离分别为 22 和 33，最大值为 33，因此输出 33。
  • 对于第二个询问，坐标 (−1,2)(-1,2) 到第 11、22、33 棵树的曼哈顿距离分别为 33、22、22，最大值为 33，因此输出 33。
  • 第三个询问将第 11 棵树的坐标更改为 (0,1)(0,1)。此时 11、22、33 棵树的坐标依次为 (0,1)(0,1)、(1,2)(1,2)、(−2,1)(-2,1)。
  • 对于第四个询问，坐标 (−1,2)(-1,2) 到第 11、22、33 棵树的曼哈顿距离分别为 22、22、22，最大值为 22，因此输出 22。

数据范围

  • 1≤N,Q≤2×1051 \leq N, Q \leq 2 \times 10^5
  • −109≤Xi,Yi≤109-10^9 \leq X_i, Y_i \leq 10^9
  • 1≤i≤N1 \leq i \leq N
  • 1≤L≤R≤N1 \leq L \leq R \leq N
  • −109≤x,y≤109-10^9 \leq x, y \leq 10^9
  • 所有输入值均为整数。

由 ChatGPT 5 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页