自动搬运

查看原文

来自洛谷，原作者为

	wurzang e

搬运于2025-08-24 21:45:17，当前版本为作者最后更新于2020-07-29 14:53:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

来补一个动态 dp 做法。

题意大致就是单点修改求最大独立集

暴力 dp 大概就是

$$\begin{cases} f_{i,0}=\max\limits \{ f_{i-1,0},f_{i-1,1}\} \\ f_{i,1}=f_{i-1,0}+a_i \end{cases} $$

最后是要求 $\max\{ f_{n,0},f_{n,1} \}$

考虑这个东西怎么转为矩阵形式。

这里我们定义矩阵乘法为

$$c_{i,j}=\max\limits_{k} \{ a_{i,k}+b_{k,j} \}$$

这个东西是满足结合律的。

于是上面那个暴力 dp 可以看成是

$$\begin{bmatrix}f_{i-1,0}\\ f_{i-1,1}\end{bmatrix} \begin{bmatrix}0 \ \ \ \ \ 0 \\ a_i\ \operatorname{-inf} \end{bmatrix}= \begin{bmatrix} f_{i,0} \\f_{i,1} \end{bmatrix} $$

然后用线段树维护矩阵乘即可。

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1
const int N=40000+5;
// f[i][0]=max(f[i-1][0],f[i-1][1])
// f[i][1]=f[i-1][0]+a[i]
// |  0 0      |  
// |  a_i -inf |
struct mat{
	int a[2][2];
	mat(){
		memset(a,-0x3f,sizeof(a));
	}
	mat operator *(const mat &b) const{
		mat res;
		for(int i=0;i<2;++i)
			for(int j=0;j<2;++j)
				for(int k=0;k<2;++k)
					res.a[i][j]=max(res.a[i][j],a[i][k]+b.a[k][j]);
		return res;
	}
}tr[N<<2];
int a[N];
void pushup(int p){
	tr[p]=tr[rs]*tr[ls];
}
void build(int p,int l,int r){
	if(l==r){
		tr[p].a[0][0]=0;
		tr[p].a[0][1]=0;
		tr[p].a[1][0]=a[l];
		tr[p].a[1][1]=-0x3f3f3f3f;
		return;
	}
	int mid=(l+r)>>1;
	build(ls,l,mid);
	build(rs,mid+1,r);
	pushup(p);
}
void upt(int p,int l,int r,int pos,int v){
	if(l==r){
		tr[p].a[0][0]=0;
		tr[p].a[0][1]=0;
		tr[p].a[1][0]=v;
		tr[p].a[1][1]=-0x3f3f3f3f;
		return;		
	}
	int mid=(l+r)>>1;
	if(pos<=mid) upt(ls,l,mid,pos,v);
	else upt(rs,mid+1,r,pos,v);
	pushup(p);
}
int main(){
	long long ans=0;
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;++i)
		cin>>a[i];
	int pos,v;
	build(1,1,n);
	mat res,tmp;
	res.a[0][0]=0;res.a[0][1]=0;
	while(q--){
		cin>>pos>>v;
		upt(1,1,n,pos,v);
		tmp=res*tr[1];
		ans+=max(tmp.a[0][0],tmp.a[0][1]);
		//cout<<max(tmp.a[0][0],tmp.a[0][1])<<endl;
	}
	cout<<ans;
	return 0;
}