数据范围
N≤500000,M≤100000N≤500000,M≤100000,
−1000≤A[i]≤1000−1000≤A[i]≤1000
输入样例：
5 3
1 2 -3 4 5
1 2 3
2 2 -1
1 3 2
输出样例：
2
-1
//1. lmax:左端点起的向右的最大子段和
//2. rmax:右端点起的向左的最大子段和
//3. dat整个区间的最大子段和
//4. sum:区间和
//这个题是单点修改，区间查询
#include<iostream>
#include<algorithm>
using namespace std;
const int maxn=4e6+100;
struct node{
int lmax,rmax,sum,dat;
int l,r;
}t[maxn];
int z[maxn];
void build(int p,int l,int r){
t[p].l=l;
t[p].r=r;
if(l==r){
t[p].sum=t[p].dat=t[p].lmax=t[p].rmax=z[l];
return ;
}
int mid=(t[p].l+t[p].r)/2;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
t[p].sum=(t[2*p].sum+t[2*p+1].sum);
t[p].lmax=max(t[2*p].lmax,t[2*p].sum+t[2*p+1].lmax);//左孩子的最大左字段和，和左孩子+右孩子的最大左字段和
t[p].rmax=max(t[2*p+1].rmax,t[2*p+1].sum+t[2*p].rmax);//右孩子的最大有子段和，右孩子+左孩子的最大右子段和
t[p].dat=max(max(t[2*p].dat,t[2*p+1].dat),t[2*p].rmax+t[2*p+1].lmax);//左右中三部分
}
void change(int p,int x,int k){
if(t[p].l==t[p].r){
t[p].dat=t[p].lmax=t[p].rmax=t[p].sum=k;
return ;
}
int mid=(t[p].l+t[p].r)/2;
if(x<=mid){
change(2*p,x,k);
}
else{
change(2*p+1,x,k);
}
t[p].sum=(t[2*p].sum+t[2*p+1].sum);
t[p].lmax=max(t[2*p].lmax,t[2*p].sum+t[2*p+1].lmax);//左孩子的最大左字段和，和左孩子+右孩子的最大左字段和
t[p].rmax=max(t[2*p+1].rmax,t[2*p+1].sum+t[2*p].rmax);//右孩子的最大有子段和，右孩子+左孩子的最大右子段和
t[p].dat=max(max(t[2*p].dat,t[2*p+1].dat),t[2*p].rmax+t[2*p+1].lmax);//左右中三部分
}
node query(int p,int l,int r){
if(t[p].l>=l&&t[p].r<=r){
return t[p];
}
int mid=(t[p].l+t[p].r)/2,val=-(1<<30);
node a,b,c;
a.lmax=a.rmax=a.sum=a.dat=val;
b.dat=b.lmax=b.rmax=b.sum=val;
c.sum=0;
if(l<=mid){
a=query(2*p,l,r);
c.sum+=a.sum;
}
if(r>mid){
b=query(2*p+1,l,r);
c.sum+=b.sum;
}
c.dat=max(max(a.dat,b.dat),a.rmax+b.lmax);
c.lmax=max(a.lmax,b.lmax+a.sum);
c.rmax=max(b.rmax,b.sum+a.rmax);
if(l>mid){
c.lmax=max(c.lmax,b.lmax);
}
if(r<=mid){
c.rmax=max(c.rmax,a.rmax);
}
return c;
}
int n,m;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>z[i];
}
build(1,1,n);
int x,y,op;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&op,&x,&y);
if(op==2){
change(1,x,y);
}
else{
if (x>y)
swap(x,y);
printf("%d\n",query(1,x,y).dat);
}
}
}
给定长度为 NN 的数列 AA，以及 MM 条指令，每条指令可能是以下两种之一：
-
1 x y，查询区间 [x,y][x,y] 中的最大连续子段和，即 maxx≤l≤r≤ymaxx≤l≤r≤y{∑i=lrA[i]∑i=lrA[i]}。 -
2 x y，把 A[x]A[x] 改成 yy。
对于每个查询指令，输出一个整数表示答案。
输入格式
第一行两个整数 N,MN,M。
第二行 NN 个整数 A[i]A[i]。
接下来 MM 行每行 33 个整数 k,x,yk,x,y，k=1k=1 表示查询（此时如果 x>yx>y，请交换 x,yx,y），k=2k=2 表示修改。
输出格式
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
数据范围
N≤500000,M≤100000N≤500000,M≤100000,
−1000≤A[i]≤1000