Truy vấn Pizzeria

Đ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$ tòa nhà trên một con phố, tòa thứ $i$ có giá pizza là $p_{i}$ . Chi phí đặt pizza từ tòa $a$ đến tòa $b$ là $p_{a} + | a - b |$ . Xử lý $q$ truy vấn:

1 k x — Thay đổi giá pizza của tòa $k$ thành $x$ .
2 k — Tìm chi phí nhỏ nhất để đặt pizza khi đang ở tòa $k$ (có thể đặt từ bất kỳ tòa nào).

Dữ liệu vào

Dòng đầu: hai số nguyên $n$ và $q$ .
Dòng thứ hai: $n$ số nguyên $p_{1}, p_{2}, \dots, p_{n}$ .
$q$ dòng tiếp theo: mỗi dòng là 1 k x hoặc 2 k.

Dữ liệu ra

Với mỗi truy vấn loại 2, in ra một dòng chứa chi phí nhỏ nhất.

Ràng buộc

$1 \leq n, q \leq 2 \times 10^{5}$
$1 \leq p_{i}, x \leq 10^{9}$
$1 \leq k \leq n$

Ví dụ

Input	Output	Giải thích
6 3 8 6 4 5 7 5 2 2 1 5 1 2 2	5 4	Truy vấn `2 2`: chi phí từ tòa 3 là $4 + \| 3 - 2 \| = 5$ . Sau cập nhật giá tòa 5 thành 1, truy vấn `2 2`: chi phí từ tòa 5 là $1 + \| 5 - 2 \| = 4$ .

Bình luận

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