GSS SPOJ – Đoạn con có tổng lớn nhất

Nguồn đề bài: http://vn.spoj.com/problems/GSS/

1. Đề bài GSS SPOJ

Cho dãy số a[1], a[2], …, a[n] (|a[i]| <= 15000, n <= 50000).

Hàm q(x, y) = max { tổng(a[i]+a[i+1]+…+a[j]), x <= i <= j <= y }.

Cho m câu hỏi dạng x, y (1 <= x <= y <= n). (m <= 50000) -> hãy tính các q(x, y).

Input

– Dòng đầu là n.

– Dòng thứ hai là dãy a.

– Dòng thứ 3 là m.

– m dòng tiếp theo mỗi dòng là 1 cặp số x, y.

Output

-> Lần lượt ghi ra các q(x, y) tương ứng. Mỗi kết quả ghi trên 1 dòng.

Example

Input:
3
-1 2 3
1
1 2
Output:
2

2. Thuật toán GSS SPOJ

Dùng cây IT với mỗi nút r ta sẽ lưu 4 giá trị: đoạn con có tổng lớn nhất bên trái(left), bên phải (right), tổng của các phần tử của cây con nút r (sum), tổng đoạn con lớn nhất (ans).

Để khởi tạo được những giá trị này ta có công thức như sau:

Sau khi đã tính đc như trên,với mỗi truy vấn q(x,y): nếu nút r đang xét nằm gọn trong khoảng cần tìm thì trả về cả 1 cặp 4 phần tử (left,right,sum,ans). Nếu hoàn toàn nằm ngoài khoảng đang xét thì trả về sum=0, left=right=ans=-oo;

Trường hơp còn lại thì trả về giá trị lớn nhất hơp bởi 2 nút con.kết quả cần in ra chính là it[r].ans;

Mình nói hơi kho hiểu, có gì thắc mắc các bạn để lại cmt phía dưới, mình sẽ giải đáp cho nhé.

3. Code tham khảo GSS SPOJ

One thought on “GSS SPOJ – Đoạn con có tổng lớn nhất

Trả lời

Thư điện tử của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *