MULDIM

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Tác giả:
Flower_On_Stone
Dạng bài
Điểm: 2300 Thời gian: 3.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Cho \(n\) điểm trên không gian \(k\) chiều, điểm thứ \(i\) có tọa độ là \((a_{i,1}, a_{i,2}, \dots, a_{i,k})\). Khoảng cách manhattan giữa \(2\) điểm \(x\) và \(y\) là: \(\sum_{i=1}^{k} |a_{x,i}-a_{y,i}|\).

Bạn phải xử lý \(q\) truy vấn thuộc \(1\) trong \(2\) loại:

  • \(1 \; i \; b_1 \; b_2 \dots \; b_k\): Gán tọa độ điểm thứ \(i\) là \((b_1,b_2,\dots,b_k)\).

  • \(2 \; l \; r\): Tìm khoảng cách manhattan lớn nhất giữa \(2\) điểm \(i\) và \(j\) với \(l \le i,j \le r\).

Input

  • Dòng \(1\): Gồm \(2\) số nguyên \(n\) và \(k\) (\(1 \le n \le 10^5\); \(1 \le k \le 5\)) - số lượng phần tử trong \(a\) và số chiều của không gian.
  • \(n\) dòng tiếp theo, mỗi dòng chứa \(k\) số \(a_{i,1},a_{i,2},\dots,a_{i,k}\) \((-10^6 \le a_{i,j} \le 10^6)\) - tọa độ điểm \(i\).
  • Dòng tiếp theo gồm \(1\) số nguyên \(q\) \((1 \le q \le 10^5)\)- số lượng truy vấn.
  • \(q\) dòng tiếp theo, mỗi dòng gồm \(1\) trong \(2\) loại:
    • \(1 \; i \; b_1 \; b_2 \dots \; b_k\) \((1 \le i \le n;\)\(-10^6 \le b_j \le 10^6)\) - Gán tọa độ điểm thứ \(i\) là \((b_1,b_2,\dots,b_k)\).
    • \(2 \; l \; r\) \((1 \le l \le r \le n)\) - Tìm khoảng cách manhattan lớn nhất giữa \(2\) đểm \(i,j\) với \(l \le i,j \le r\).

Output

  • Với mỗi truy vấn loại \(2\), đưa ra \(1\) dòng gồm \(1\) số duy nhất là kết quả tìm được.

Scoring

  • Subtask \(1\) (\(30\%\) số điểm\()\): \(n,q \le 3000\)
  • Subtask \(2\) (\(20\%\) số điểm\()\): \(k = 1\).
  • Subtask \(3\) (\(20\%\) số điểm\()\): \(k = 2\).
  • Subtask \(4\) (\(30\%\) số điểm\()\): Không có điều kiện gì thêm.

Example

Test 1

Input 
5 2
1 2
2 3
3 4
4 5
5 6
7
2 1 5
2 1 3
2 3 5
1 5 -1 -2
2 1 5
1 4 -1 -2
2 1 5
Output 
8
4
4
12
10

Bình luận