Truy vấn Tổng Đoạn Con Lớn Nhất II

Đ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 và $q$ truy vấn. Với mỗi truy vấn $(a, b)$ , tính tổng lớn nhất của một đoạn con liên tiếp trong phạm vi $[a, b]$ (đoạn rỗng có tổng bằng 0).

Dữ liệu vào

Dòng đầu: hai số nguyên $n$ và $q$ .
Dòng thứ hai: $n$ số nguyên $x_{1}, x_{2}, \dots, x_{n}$ .
$q$ dòng tiếp theo: mỗi dòng chứa hai số $a$ và $b$ .

Dữ liệu ra

Với mỗi truy vấn, in ra một dòng chứa tổng đoạn con lớn nhất trong $[a, b]$ .

Ràng buộc

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

Ví dụ

Input	Output	Giải thích
8 4 2 5 1 -2 3 -1 -7 1 2 4 2 5 6 7 4 8	6 7 0 3	[2,4]: [5,1] = 6. [2,5]: [5,1,-2,3] = 7. [6,7]: [-1,-7] âm, đoạn rỗng = 0. [4,8]: [-2,3] = 3... thực ra max là [3] = 3 hoặc [-2,3] = 1, nên max = 3.
5 3 -3 2 4 -1 5 1 5 1 3 3 5	10 6 8	[1,5]: [2,4,-1,5] = 10. [1,3]: [2,4] = 6. [3,5]: [4,-1,5] = 8.

Bình luận

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