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 ...
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:
1 2 3 4 | it[r].sum=it[2*r].sum+it[2*r+1].sum; it[r].left=max(it[2*r].left,it[2*r].sum+it[2*r+1].left); it[r].right=max(it[2*r+1].right,it[2*r+1].sum+it[2*r].right); it[r].ans=max(max(it[2*r].ans,it[2*r+1].ans),it[2*r].right+it[2*r+1].left); |
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | //saker1417 #include <bits/stdc++.h> #define left first.first #define right first.second #define sum second.first #define ans second.second #define maxn 50001 #define oo 1000000001 using namespace std; long long n,a[maxn],m; typedef pair < long long , long long > II; typedef pair < II , II > IIII; IIII it[4*maxn]; void doc() { cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; } void khoitao(int r,int k,int l) { if(k==l) { it[r]=IIII(II(a[k],a[k]),II(a[k],a[k])); return; } int g=(k+l)/2; khoitao(2*r,k,g); khoitao(2*r+1,g+1,l); it[r].sum=it[2*r].sum+it[2*r+1].sum; it[r].left=max(it[2*r].left,it[2*r].sum+it[2*r+1].left); it[r].right=max(it[2*r+1].right,it[2*r+1].sum+it[2*r].right); it[r].ans=max(max(it[2*r].ans,it[2*r+1].ans),it[2*r].right+it[2*r+1].left); } IIII get(int r,int k,int l,int u,int v) { if(v<k||l<u) return IIII(II(0,-oo),II(-oo,-oo)); if(u<=k&&l<=v) return it[r]; int g=(k+l)/2; IIII t1=get(2*r,k,g,u,v); IIII t2=get(2*r+1,g+1,l,u,v); long long left1=max(t1.left,t1.sum+t2.left); long long right1=max(t2.right,t2.sum+t1.right); long long ans1=max(max(t1.ans,t2.ans),t1.right+t2.left); long long sum1=t1.sum+t2.sum; return IIII(II(left1,right1),II(sum1,ans1)); } void tinh() { khoitao(1,1,n); int m; cin>>m; while(m--) { int u,v; cin>>u>>v; cout<<get(1,1,n,u,v).ans<<endl; } } int main() { freopen("GSS.inp","r",stdin); freopen("GSS.out","w",stdout); ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); doc(); tinh(); } |
