GSS3 - Can you answer these queries III
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
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
const int INF=;
int n,Q,a[maxn]; struct Node{
int lx,rx,mx,sum;
Node(int _lx=-INF,int _rx=-INF,int _mx=-INF){
lx=_lx;rx=_rx;mx=_mx;
}
}T[maxn<<]; void Push_up(Node &x,Node l,Node r){
x.sum=l.sum+r.sum;
x.lx=max(l.lx,l.sum+r.lx);
x.rx=max(r.rx,r.sum+l.rx);
x.mx=max(max(l.mx,r.mx),l.rx+r.lx);
} void Build(int x,int l,int r){
if(l==r){
T[x].lx=T[x].rx=max(a[l],);
T[x].mx=T[x].sum=a[l];
return;
}
int mid=(l+r)>>;
Build(x<<,l,mid);
Build(x<<|,mid+,r);
Push_up(T[x],T[x<<],T[x<<|]);
} void Modify(int x,int l,int r,int g){
if(l==r){
T[x].lx=T[x].rx=max(a[l],);
T[x].mx=T[x].sum=a[l];
return;
}
int mid=(l+r)>>;
if(mid>=g)Modify(x<<,l,mid,g);
else Modify(x<<|,mid+,r,g);
Push_up(T[x],T[x<<],T[x<<|]);
} Node Query(int x,int l,int r,int a,int b){
if(l>=a&&r<=b)
return T[x];
int mid=(l+r)>>;
Node L,R,ret;
if(mid>=a)L=Query(x<<,l,mid,a,b);
if(mid<b)R=Query(x<<|,mid+,r,a,b);
Push_up(ret,L,R);
return ret;
} int main(){
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
Build(,,n);
scanf("%d",&Q);
int tp,x,y;
while(Q--){
scanf("%d%d%d",&tp,&x,&y);
if(!tp)
a[x]=y,Modify(,,n,x);
else
printf("%d\n",Query(,,n,x,y).mx);
}
return ;
}
水题。