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

Problem

https://vn.spoj.com/problems/GSS

https://oj.vnoi.info/problem/GSS

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  

Tutorial

Bài này sử dụng segment tree, trong đó mỗi node lưu lại các thông tin:

sum: tổng giá trị các phần tử trên đoạn
prefix: tiền tố lớn nhất trên đoạn
suffix: hậu tố lớn nhất trên đoạn
best: tổng lớn nhất trong đoạn

Khi merge hay combine hai node con vào node cha trên cây segment, ta dễ dàng có được các công thức sau:

sum       = l.sum + r.sum;
prefix    = max(l.prefix, l.sum + r.prefix);
suffix    = max(r.suffix, r.sum + l.suffix);
best      = max(l.best, r.best, l.suffix + r.prefix);
// trong đó: l, r là hai node con của node cần merge.

Submission

GSS.cpp

Tutorial SPOJ