http://www.spoj.com/problems/GSS3/
You are given a sequence A of N (N <= 50000) integers between
-10000 and 10000. On this sequence you have to apply M (M <= 50000)
operations:
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
modify the i-th element in the sequence or for given x y print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
Input
The first line of input contains an integer N. The following line contains N integers, representing the sequence A1..AN.The third line contains an integer M. The next M lines contain the operations in following form:
0 x y: modify Ax into y (|y|<=10000).
1 x y: print max{Ai + Ai+1 + .. + Aj | x<=i<=j<=y }.
Output
For each query, print an integer as the problem required.Example
Input: 4 1 2 3 4 4 1 1 3 0 3 -3 1 2 4 1 3 3 Output: 6 4 -3
This is solution for spoj problem GSS3 problem
#include <bits/stdc++.h> using namespace std; int a[50001]; struct segNode { int left,right,segsum,ans; }t[4*50000]; int maxi(int a,int b,int c) { return max(max(a,b),c); } void merge(struct segNode &e,struct segNode a,struct segNode b) { e.segsum=a.segsum+b.segsum; e.left=max(a.left,a.segsum+b.left); e.right=max(b.right,b.segsum+a.right); e.ans=maxi(a.ans,b.ans,a.right+b.left); } void build(int low,int high,int pos) { if(low==high) { t[pos].left=t[pos].right=t[pos].segsum=t[pos].ans=a[low]; return; } int mid=(low+high)/2; build(low,mid,pos<<1); build(mid+1,high,pos<<1|1); merge(t[pos],t[pos<<1],t[pos<<1|1]); } void query(segNode &res,int pos,int l,int r,int ql,int qr) { if(l==ql&&r==qr) { res=t[pos]; } else { int cl=pos<<1; int cr=cl|1; int mid=((l+r)>>1); if(qr<=mid) { query(res,cl,l,mid,ql,qr); } else if(ql>mid) { query(res,cr,mid+1,r,ql,qr); } else { segNode lefti,righti; query(lefti,cl,l,mid,ql,mid); query(righti,cr,mid+1,r,mid+1,qr); merge(res,lefti,righti); } } } void modify(int pos,int val,int l,int r,int point) { if(l==r) { t[point].left=t[point].right=t[point].segsum=t[point].ans=val; return; } int mid=(l+r)>>1; int cl=point<<1; int cr=cl|1; if(pos<=mid) { modify(pos,val,l,mid,cl); } else { modify(pos,val,mid+1,r,cr); } merge(t[point],t[cl],t[cr]); } int main() { int i,j,k,n,m,x,y,q,ql,qr,op; scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); build(1,n,1); scanf("%d",&q); for(int uu=0;uu<q;uu++) { scanf("%d %d %d",&op,&ql,&qr); segNode s; if(op==1) { query(s,1,1,n,ql,qr); printf("%d\n",s.ans); } if(op==0) { modify(ql,qr,1,n,1); } } return 0;}
No comments:
Post a comment