Truy vấn Mảng Tăng dần

Đ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

Cho mảng $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ . Với mỗi truy vấn cho đoạn $[a, b]$ , hãy tính số phép tăng tối thiểu (mỗi phép tăng một phần tử lên 1) để đoạn con $x_{a}, x_{a + 1}, \dots, x_{b}$ trở thành không giảm (tức $x_{i} \leq x_{i + 1}$ với mọi $i$ ).

Dữ liệu vào

Dòng 1: Hai số nguyên $n$ và $q$ ( $1 \leq n, q \leq 2 \times 10^{5}$ ).
Dòng 2: $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ ( $1 \leq x_{i} \leq 10^{9}$ ).
$q$ dòng tiếp theo: Mỗi dòng gồm hai số nguyên $a$ và $b$ ( $1 \leq a \leq b \leq n$ ).

Dữ liệu ra

Với mỗi truy vấn, in ra số phép tăng tối thiểu trên một dòng.

Ràng buộc

$1 \leq n, q \leq 2 \times 10^{5}$
$1 \leq x_{i} \leq 10^{9}$
$1 \leq a \leq b \leq n$

Ví dụ

Input	Output	Giải thích
5 3 2 10 4 2 5 3 5 2 2 1 4	2 0 14	Đoạn [3,5]=[4,2,5]: tăng thành [4,4,5], tốn 2 phép. Đoạn [2,2]=[10]: đã không giảm. Đoạn [1,4]=[2,10,4,2]: tăng thành [2,10,10,10], tốn $(10 - 4) + (10 - 2) = 14$ phép.
4 2 5 3 2 1 1 4 2 3	9 1	Đoạn [1,4]=[5,3,2,1]: tăng thành [5,5,5,5], tốn $(5 - 3) + (5 - 2) + (5 - 1) = 9$ phép. Đoạn [2,3]=[3,2]: tăng thành [3,3], tốn 1 phép.

Ghi chú

Để đoạn $[a, b]$ không giảm với chi phí nhỏ nhất, ta chỉ được tăng (không giảm) phần tử. Phần tử thứ $i$ sau khi tối ưu bằng $max (x_{a}, x_{a + 1}, \dots, x_{i})$ . Chi phí là $\sum_{i = a}^{b} (max (x_{a}, \dots, x_{i}) - x_{i})$ .

Bình luận

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