题目
题目链接：https://www.luogu.com.cn/problem/SP1716
\(n\) 个数，\(q\) 次操作
操作0 x y把\(A_x\) 修改为\(y\)
操作1 l r询问区间\([l, r]\) 的最大子段和
思路
经典的最大子段和问题。解决这类问题一般有两种做法：
- 线段树维护区间最大子段和，最大前缀和最大后缀。
- 动态\(dp\)。
方法1在很久以前就做过了，刚接触\(ddp\)，来做一下\(ddp\)的模板题。
我们考虑如果是静态最大子段和应该怎么做。设\(f[i]\)表示以\(i\)结尾的最大后缀，那么有
\[f[i]=max(f[i-1]+a[i],a[i])
\]
则答案就是\(\max^{n}_{i=1}f[i]\)。
考虑用矩阵乘法优化，但是一般的矩阵乘法是不支持\(\min,\max\)两种操作的，但是矩阵乘法满足分配律，而\(\max\)也依然满足分配律，所以我们令
\[f_{i,j}=\max^{n}_{k=1}(a_{i,k}+b_{k,j})
\]
再进行矩阵乘法。
那么可以写出转移矩阵
\[\begin{bmatrix}
f[i]\\
ans[i]\\
0
\end{bmatrix}
\begin{bmatrix}
a[i] & -\infty & a[i]\\
a[i] & 0 & a[i]\\
-\infty & -\infty &0
\end{bmatrix}
=
\begin{bmatrix}
a[i+1]\\
ans[i+1]\\
0
\end{bmatrix}\]
其中\(ans[i]=\max^{n}_{i=1}f[i]\)
考虑到矩阵乘法满足结合律，所以我们可以用线段树维护矩阵区间积。这样就可以支持单点修改和区间查询。
时间复杂度\(O(q·k^3\log^2 n )\)，其中\(k=3\)。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=50010,Inf=1e9;
int n,Q,opt,x,y,a[N];
struct matrix
{
int a[4][4];
friend matrix operator *(matrix a,matrix b)
{
matrix c;
memset(c.a,-0x3f3f3f3f,sizeof(c.a));
for (int i=1;i<=3;i++)
for (int j=1;j<=3;j++)
for (int k=1;k<=3;k++)
c.a[i][j]=max(c.a[i][j],a.a[i][k]+b.a[k][j]);
return c;
}
};
struct SegTree
{
matrix f[N*4];
int l[N*4],r[N*4];
void pushup(int x)
{
f[x]=f[x*2]*f[x*2+1];
}
void build(int x,int ql,int qr)
{
l[x]=ql; r[x]=qr;
if (ql==qr)
{
f[x].a[1][1]=f[x].a[1][3]=f[x].a[2][1]=f[x].a[2][3]=a[ql];
f[x].a[1][2]=f[x].a[3][1]=f[x].a[3][2]=-Inf;
f[x].a[2][2]=f[x].a[3][3]=0;
return;
}
int mid=(ql+qr)>>1;
build(x*2,ql,mid); build(x*2+1,mid+1,qr);
pushup(x);
}
void update(int x,int k,int val)
{
if (l[x]==k && r[x]==k)
{
f[x].a[1][1]=f[x].a[1][3]=f[x].a[2][1]=f[x].a[2][3]=val;
return;
}
int mid=(l[x]+r[x])>>1;
if (k<=mid) update(x*2,k,val);
else update(x*2+1,k,val);
pushup(x);
}
matrix ask(int x,int ql,int qr)
{
if (l[x]==ql && r[x]==qr)
return f[x];
int mid=(l[x]+r[x])>>1;
if (qr<=mid) return ask(x*2,ql,qr);
if (ql>mid) return ask(x*2+1,ql,qr);
return ask(x*2,ql,mid)*ask(x*2+1,mid+1,qr);
}
}seg;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d",&a[i]);
seg.build(1,1,n);
scanf("%d",&Q);
while (Q--)
{
scanf("%d%d%d",&opt,&x,&y);
if (!opt) seg.update(1,x,y);
else
{
matrix ans=seg.ask(1,x,y);
printf("%d\n",max(ans.a[2][1],ans.a[2][3]));
}
}
return 0;
}