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
思路:
要是由浅入深的话,建议先看一下这篇,一个一个关键点来。https://blog.csdn.net/TherAndI/article/details/122714363https://blog.csdn.net/TherAndI/article/details/122714363然后和Ⅰ相比这就是多了一个单点修改change(),其他的不能说是一模一样,只能说是分毫不差,
main()函数当然要改的。
#include<iostream>
using namespace std;
typedef long long ll;
const int N=5e4;
int n,m,ch,x;
ll y;
ll a[N+5];
struct tree
{
ll sum,ans,lans,rans;
}t[N*4+5];
void pushup(int k)
{
t[k].sum =t[k*2].sum +t[k*2+1].sum ;
t[k].lans =max(t[k*2].lans ,t[k*2].sum +t[k*2+1].lans );
t[k].rans =max(t[k*2+1].rans ,t[k*2+1].sum +t[k*2].rans );
t[k].ans =max(max(t[k*2].ans ,t[k*2+1].ans ),t[k*2].rans +t[k*2+1].lans );
}
void build(int k,int l,int r)
{
if(l==r)
{
t[k].sum =t[k].ans =t[k].lans =t[k].rans =a[l];
return ;
}
int mid=(l+r)/2;
build(k*2,l,mid);
build(k*2+1,mid+1,r);
pushup(k);
}
void change(int k,int l,int r,int x,ll y)
{
if(l==r&&l==x)
{
t[k].ans =t[k].lans =t[k].rans =t[k].sum =y;
return;
}
int mid=(l+r)/2;
if(x<=mid)
change(k*2,l,mid,x,y);
else
change(k*2+1,mid+1,r,x,y);
pushup(k);
}
tree query(int k,int l,int r,int x,ll y)
{
if(x<=l&&y>=r)
return t[k];
int mid=(l+r)/2;
if(y<=mid)
return query(k*2,l,mid,x,y);
else if(x>mid)
return query(k*2+1,mid+1,r,x,y);
else
{
tree re,left,right;
left=query(k*2,l,mid,x,y);
right=query(k*2+1,mid+1,r,x,y);
re.sum =left.sum +right.sum ;
re.lans =max(left.lans ,left.sum +right.lans );
re.rans =max(right.rans ,right.sum +left.rans );
re.ans =max(max(left.ans ,right.ans ),left.rans +right.lans );
return re;
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&a[i]);
build(1,1,n);
scanf("%d",&m);
while(m--)
{
scanf("%d %d %lld",&ch,&x,&y);
if(ch==1)
{
printf("%lld\n",query(1,1,n,x,y).ans );
}
else
{
change(1,1,n,x,y);
}
}
return 0;
}