自动搬运

查看原文

来自洛谷，原作者为

	zyn0309 **

搬运于2025-08-24 22:51:52，当前版本为作者最后更新于2025-07-29 20:54:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题目传送门

思路

先考虑没有环怎么做，有一个显然的线性 DP，定义 $f_{i,j}$ 代表选到了第 $i$ 个点，结尾最多连续选了 $j$ 个点的最大值，因为每次只修改一个点，考虑放到线段树上做。设 $v_{u,i,j}$ 代表线段树上的节点 $u$，从左边连续选不超过 $i$ 个，从右边连续选不超过 $j$ 个，然后类似于朴素 DP，可以直接在线段树上合并左右儿子答案。

但是这样没有考虑环的情况，因此需要在合并线段树根节点左右儿子的时候特殊处理一下，让左儿子左边连续段长度和右儿子右边连续段长度合起来也不超过 $4$ 即可。

Code

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=4e4+10;
int n,a[N],q;
#define pb push_back
#define mk make_pair
struct tree{
	int l,r,v[4][4];//v[i][j] 从左边连续不超过 i 个，右边连续不超过 j 个的最大值
	#define lson(u) (u<<1)
	#define rson(u) (u<<1|1)
}t[4*N];
inline void push_up(int u){
	for(int a=0;a<4;++a)
	for(int b=0;b<4;++b)
	  t[u].v[a][b]=0;
	int llen=t[lson(u)].r-t[lson(u)].l+1,rlen=t[rson(u)].r-t[rson(u)].l+1;
	for(int a=0;a<4;++a)
	for(int b=0;b<4;++b)
	for(int i=0;i<4;++i)
	for(int j=0;i+j<4;++j){
	  if(a>=llen&&j&&b>=rlen&&i){
		if((a+j<4)&&(b+i<4))t[u].v[a+j][b+i]=max(t[u].v[a+j][b+i],t[lson(u)].v[a][i]+t[rson(u)].v[j][b]);
		continue;
	  }
	  if(a>=llen&&j){
		if(a+j<4)t[u].v[a+j][b]=max(t[u].v[a+j][b],t[lson(u)].v[a][i]+t[rson(u)].v[j][b]);
		continue;
	  }
	  if(b>=rlen&&i){
		if(b+i<4)t[u].v[a][b+i]=max(t[u].v[a][b+i],t[lson(u)].v[a][i]+t[rson(u)].v[j][b]);
		continue;
	  }
	  t[u].v[a][b]=max(t[u].v[a][b],t[lson(u)].v[a][i]+t[rson(u)].v[j][b]);
	}
}
inline void build(int u,int l,int r){
	t[u].l=l;
	t[u].r=r;
	if(l==r){
	  for(int i=1;i<4;++i)
	  for(int j=1;j<4;++j)
	    t[u].v[i][j]=a[l];
	  return;
	}
	int mid=(l+r)>>1;
	build(lson(u),l,mid);
	build(rson(u),mid+1,r);
	push_up(u);
}
inline void update(int u,int x){
	if(t[u].l==t[u].r){
	  for(int i=1;i<4;++i)
	  for(int j=1;j<4;++j)
	    t[u].v[i][j]=a[x];
	  return;
	}
	int mid=(t[u].l+t[u].r)>>1;
	if(x<=mid)update(lson(u),x);
	else update(rson(u),x);
	push_up(u);
}
inline int getans(){
	if(n==1)return a[1];
	int ans=0;
	for(int a=0;a<4;++a)
	for(int b=0;a+b<4;++b)
	for(int i=0;i<4;++i)
	for(int j=0;i+j<4;++j)
	  ans=max(ans,t[2].v[a][i]+t[3].v[j][b]);
	return ans;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i)cin>>a[i];
	build(1,1,n);
	cout<<getans()<<"\n";
	cin>>q;
	int x,c;
	while(q--){
	  cin>>x>>c;
	  a[x]=c;
	  update(1,x);
	  cout<<getans()<<"\n";
	}
	return 0;
}