F - Manhattan Christmas Tree 2 解説 /

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

二次元平面上に N 個のクリスマスツリーがあります。i 番目 (1\le i\le N) のクリスマスツリーは座標 (X_i,Y_i) に存在します。

Q 個のクエリが与えられるので、順にクエリを処理してください。各クエリは、以下のいずれかです。

  • タイプ 1 : 1 i x y の形式で与えられる。i 番目のクリスマスツリーの座標を (x,y) に変更する。
  • タイプ 2 : 2 L R x y の形式で与えられる。L,L+1,\ldots,R 番目のクリスマスツリーのうち、座標 (x,y) からマンハッタン距離で最も遠いクリスマスツリーまでの距離を出力する。

ただし、座標 (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,2,3 番目のクリスマスツリーはそれぞれ座標 (-1,-1),(1,2),(-2,1) に存在します。

各クエリは以下のように処理されます。

  • 1,2 番目のクリスマスツリーと座標 (0,0) のマンハッタン距離はそれぞれ 2,3 です。したがって、 2,3 の最大値である 3 を出力します。
  • 1,2,3 番目のクリスマスツリーと座標 (-1,2) のマンハッタン距離はそれぞれ 3,2,2 です。したがって、 3,2,2 の最大値である 3 を出力します。
  • 1 番目のクリスマスツリーの座標を (0,1) に変更します。1,2,3 番目のクリスマスツリーの座標はそれぞれ (0,1),(1,2),(-2,1) になります。
  • 1,2,3 番目のクリスマスツリーと座標 (-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

Score : 500 points

Problem Statement

There are N Christmas trees on a two-dimensional plane. The i-th (1\le i\le N) Christmas tree is located at coordinates (X_i,Y_i).

You are given Q queries. Process the queries in order. Each query is one of the following:

  • Type 1 : Given in the form 1 i x y. Change the coordinates of the i-th Christmas tree to (x,y).
  • Type 2 : Given in the form 2 L R x y. Output the Manhattan distance from the coordinates (x,y) to the farthest Christmas tree among the L,L+1,\ldots,R-th Christmas trees.

Here, the Manhattan distance between coordinates (x_1,y_1) and coordinates (x_2,y_2) is defined as |x_1-x_2|+|y_1-y_2|.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Here, the i-th query \text{query}_i is given in one of the following formats:

1 i x y

2 L R x y

Output

Output the answers to the queries, separated by newlines, according to the instructions in the problem statement.

Sample Input 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

Sample Output 1

3
3
2

Initially, the 1st, 2nd, 3rd Christmas trees are located at coordinates (-1,-1), (1,2), (-2,1), respectively.

Each query is processed as follows:

  • The Manhattan distances from the 1st and 2nd Christmas trees to coordinates (0,0) are 2 and 3, respectively. Thus, output 3, which is the maximum value among 2,3.
  • The Manhattan distances from the 1st, 2nd, 3rd Christmas trees to coordinates (-1,2) are 3, 2, 2, respectively. Thus, output 3, which is the maximum value among 3,2,2.
  • Change the coordinates of the 1st Christmas tree to (0,1). The coordinates of the 1st, 2nd, 3rd Christmas trees become (0,1),(1,2),(-2,1), respectively.
  • The Manhattan distances from the 1st, 2nd, 3rd Christmas trees to coordinates (-1,2) are 2, 2, 2, respectively. Thus, output 2, which is the maximum value among 2,2,2.

Sample Input 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

Sample Output 2

24
24
22
30
9