Editorial for GSS3 problem SPOJ - UCS - Unleash-Coding-Skills

## Sunday, 4 March 2018

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 }.

### 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;

}
```