Marathon (Gold)

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

Có $N$ điểm kiểm tra trên mặt phẳng. Một vận động viên đi từ điểm $I$ đến điểm $J$ (theo thứ tự $I, I + 1, \dots, J$ ), và được phép bỏ qua đúng một điểm kiểm tra trung gian (không được bỏ điểm $I$ hoặc $J$ ) để rút ngắn quãng đường.

Khoảng cách giữa hai điểm được tính theo khoảng cách Manhattan: $| x_{1} - x_{2} | + | y_{1} - y_{2} |$ .

Cho $Q$ truy vấn, mỗi truy vấn là một trong hai loại:

U k x y — cập nhật toạ độ điểm $k$ thành $(x, y)$ .
Q I J — hỏi quãng đường ngắn nhất từ $I$ đến $J$ (có thể bỏ qua một điểm trung gian).

Dữ liệu vào

Dòng đầu chứa hai số nguyên $N$ và $Q$ .

$N$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $x_{i}$ , $y_{i}$ — toạ độ điểm kiểm tra thứ $i$ .
$Q$ dòng tiếp theo, mỗi dòng là truy vấn dạng U k x y hoặc Q I J (với $1 \leq I < J \leq N$ ).

Dữ liệu ra

Với mỗi truy vấn Q I J, in ra quãng đường ngắn nhất trên một dòng.

Ràng buộc

$1 \leq N, Q \leq 100 000$
$- 1000 \leq x_{i}, y_{i} \leq 1000$
Với truy vấn Q: $1 \leq I < J \leq N$
Với truy vấn U: $1 \leq k \leq N$

Ví dụ

Input	Output	Giải thích
5 5 -4 4 -5 -3 -1 5 -3 4 0 5 Q 1 5 U 4 0 1 U 4 -1 1 Q 2 4 Q 1 4	11 8 8	Q(1,5): tổng=27, bỏ điểm 2 tiết kiệm 16, đáp án=11. Sau hai cập nhật điểm 4: Q(2,4): tổng=16, bỏ điểm 3 tiết kiệm 8, đáp án=8. Q(1,4): tổng=24, bỏ điểm 2 tiết kiệm 16, đáp án=8.
2 1 0 0 3 4 Q 1 2	7	Chỉ 2 điểm, không có điểm trung gian để bỏ, khoảng cách Manhattan = 3+4 = 7.

Bình luận

Không có bình luận tại thời điểm này.