Editorial for GSS3 problem SPOJ - UCS

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;


}