\(n\) 个数，\(q\) 个操作
操作 \(0\ x\ y\) 表示把 \(a_x\) 修改为 \(y\)
操作 \(1\ l\ r\) 询问 \([l,r]\) 的最大子段和
\(1\leq n,q\leq 50000,|y|\leq 10000\)
sol1
线段树做法 .
每个节点维护，前缀最大值 \(a\)，后缀最大值 \(b\)，区间内最大连续子段和 \(c\) , 区间和 \(w\) .
只有单点查询，所以只需要考虑合并操作 .
将左区间 \(l\) 和右区间 \(r\) 合并到 \(x\) .
\(x.a=\max(l.a,l.w+r.a)\) 前缀最大值在左区间 \(l.a\) ，在右区间 \(l.w+r.a\)
\(x.b=\max(r.b,r.w+l.b)\) 后缀最大值在右区间 \(r.b\) ，在左区间 \(r.w+l.b\)
\(x.c=\max(l.c,r.c,l.b+r.a)\)
区间最大连续子段和在左区间 \(l.c\)，在右区间 \(r.c\)，两个区间都有，即 \(l.b+r.a\)
\(x.w=l.w+r.w\)
知道了合并操作，区间求和，单点修改就都不在话下了 .
时间复杂度 : \(\mathrm O(q\log n)\)
空间复杂度 : \(\mathrm O(n)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while((ch<'0'||ch>'9')&&(ch!='-'))ch=getchar();
int f=false;
if(ch=='-'){
f=true;
ch=getchar();
}
int res=0;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
if(f)res=-res;
return res;
}
inline void print(int res){
if(res==0){
putchar('0');
return;
}
if(res<0){
putchar('-');
res=-res;
}
int a[10],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
const int inf=1e9+10;
class node{public:int a,b,c,w;}tree[50010<<2];
int a[50010];
void pu(node &x,node l,node r){
x.a=max(l.a,l.w+r.a);
x.b=max(r.b,r.w+l.b);
x.c=max(l.b+r.a,max(l.c,r.c));
x.w=l.w+r.w;
}
void build(int x,int l,int r){
if(l==r){
tree[x]=(node){a[l],a[l],a[l],a[l]};
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
pu(tree[x],tree[x<<1],tree[x<<1|1]);
}
void upd(int x,int l,int r,int pos,int val){
if(l==r){
tree[x]=(node){val,val,val,val};
return;
}
int mid=(l+r)>>1;
if(pos<=mid)upd(x<<1,l,mid,pos,val);
else upd(x<<1|1,mid+1,r,pos,val);
pu(tree[x],tree[x<<1],tree[x<<1|1]);
}
node qry(int x,int l,int r,int cl,int cr){
if(l==cl&&cr==r)return tree[x];
int mid=(l+r)>>1;
if(cr<=mid)return qry(x<<1,l,mid,cl,cr);
if(cl>=mid+1)return qry(x<<1|1,mid+1,r,cl,cr);
node res;
pu(res,qry(x<<1,l,mid,cl,mid),qry(x<<1|1,mid+1,r,mid+1,cr));
return res;
}
int n,q;
int main(){
n=read();
for(int i=0;i<n;i++)a[i]=read();
build(1,0,n-1);
q=read();
for(int i=0;i<q;i++){
int type=read();
if(type==0){
int x=read()-1,val=read();
upd(1,0,n-1,x,val);
}
else{
int l=read()-1,r=read()-1;
print(qry(1,0,n-1,l,r).c);
putchar('\n');
}
}
return 0;
}
/*inline? ll or int? size? min max?*/
sol2
\(ddp\) 做法.
考虑两个 \(dp\) ,
\(f(i)\) 表示以 \(i\) 结束的连续子序列最大值 .
\(g(i)\) 表示区间 \([0,i]\) 的连续子序列最大值 .
考虑转移方程，
\(f(i)=\max(a_i,f(i-1)+a_i)\)
\(g(i)=\max(f(i),g(i-1))\) 即 \(g(i)=\max(f(i),f(i-1)+a_i,a_i)\)
\(f(i),g(i)\) 都是从 \(f(i-1),g(i-1)\) 转移过来的，考虑转移矩阵. 这个的矩阵是广义矩阵，依旧满足结合律 .
\[\begin{bmatrix} a_i&−\infty&a_i\\ a_i&0&a_i\\ -\infty&-\infty&0\\ \end{bmatrix} \begin{bmatrix} f(i-1)\\ g(i-1)\\ 0 \end{bmatrix} = \begin{bmatrix} f(i)\\ g(i)\\ 0 \end{bmatrix} \]这个的矩阵是广义矩阵，依旧满足结合律 .
矩阵写得有点奇怪，因为矩阵的计算要从下标从大往小算 .
不带修改的时候，矩阵快速幂就可以解决 .
但是带上修改操作，就需要用线段树维护，每个节点维护当前区间的转移矩阵 .
修改和查询和普通的线段树一样，只是 pushup 操作是两个矩阵相乘 .
合并的时候注意，因为我写的转移矩阵下表要从大往小算，所以，合并的时候是右儿子乘左儿子 .
其实也可以写得正常一点，转移矩阵就是
\[\begin{bmatrix} f(i-1)&g(i-1)&0 \end{bmatrix} \begin{bmatrix} a_i&a_i&-\infty\\ -\infty&0&-\infty\\ a_i&a_i&0\\ \end{bmatrix} = \begin{bmatrix} f(i),g(i),0 \end{bmatrix} \]此时下标就正常了，是从左往右合并 .
时间复杂度 : \(\mathrm O(27q\log n)\)
空间复杂度 : \(O(27n)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while((ch<'0'||ch>'9')&&(ch!='-'))ch=getchar();
bool f=false;
if(ch=='-'){
f=true;
ch=getchar();
}
int res=0;
while(ch>='0'&&ch<='9'){
res=(res<<3)+(res<<1)+ch-'0';
ch=getchar();
}
if(f)res=-res;
return res;
}
inline void print(int res){
if(res==0){
putchar('0');
return;
}
if(res<0){
putchar('-');
res=-res;
}
int a[10],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
const int inf=1e9+10;
int v[50010<<2];
class node{
public:
int a[3][3];
}t[50010<<2];
inline node operator*(const node&x,const node&y){
node res;
for(int i=0;i<3;i++)for(int j=0;j<3;j++)
res.a[i][j]=-inf;
for(int k=0;k<3;k++){
for(int i=0;i<3;i++)for(int j=0;j<3;j++){
if(x.a[i][k]==-inf||y.a[k][j]==-inf)continue;
res.a[i][j]=max(res.a[i][j],x.a[i][k]+y.a[k][j]);
}
}
return res;
}
node pu(const node&x,const node&y){
node res;
for(int i=0;i<3;i++)for(int j=0;j<3;j++)res.a[i][j]=-inf;
res=x*y;
return res;
}
void build(int x,int l,int r){
if(l==r){
t[x].a[0][0]=v[l];t[x].a[0][1]=-inf;t[x].a[0][2]=v[l];
t[x].a[1][0]=v[l];t[x].a[1][1]=0;t[x].a[1][2]=v[l];
t[x].a[2][0]=-inf;t[x].a[2][1]=-inf;t[x].a[2][2]=0;
return;
}
int mid=(l+r)>>1;
build(x<<1,l,mid);
build(x<<1|1,mid+1,r);
t[x]=pu(t[x<<1|1],t[x<<1]);
/* for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
cout<<t[x].a[i][j]<<" ";
}
cout<<endl;
}
*/
}
void upd(int x,int l,int r,int pos,int val){
if(l==r){
t[x].a[0][0]=val;t[x].a[0][1]=-inf;t[x].a[0][2]=val;
t[x].a[1][0]=val;t[x].a[1][1]=0;t[x].a[1][2]=val;
t[x].a[2][0]=-inf;t[x].a[2][1]=-inf;t[x].a[2][2]=0;
return;
}
int mid=(l+r)>>1;
if(pos<=mid)upd(x<<1,l,mid,pos,val);
else upd(x<<1|1,mid+1,r,pos,val);
t[x]=pu(t[x<<1|1],t[x<<1]);
/* for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
cout<<t[x].a[i][j]<<" ";
}
cout<<endl;
}
*/
}
node qry(int x,int l,int r,int cl,int cr){
if(cl==l&&cr==r)return t[x];
int mid=(l+r)>>1;
if(cr<=mid)return qry(x<<1,l,mid,cl,cr);
if(mid+1<=cl)return qry(x<<1|1,mid+1,r,cl,cr);
return qry(x<<1|1,mid+1,r,mid+1,cr)*qry(x<<1,l,mid,cl,mid);
}
int n,q;
int main(){
n=read();
for(int i=0;i<n;i++)v[i]=read();
build(1,0,n-1);
q=read();
for(int i=0;i<q;i++){
int type=read();
if(type==0){
int id=read()-1,val=read();
upd(1,0,n-1,id,val);
}
else{
int l=read()-1,r=read()-1;
node matrix=qry(1,0,n-1,l,r);
print(max(max(matrix.a[0][2],matrix.a[1][2]),matrix.a[0][3]));
putchar('\n');
}
}
return 0;
}
/*inline? ll or int? size? min max?*/
/*
4
1 2 3 4
4
1 1 3
0 3 -3
1 2 4
1 3 3
*/