看到题目没有什么思路，我们可以先尝试爆搜这个过程。

对于当前这块饼干，我们可以直接枚举 Aurora 和 Bianca 选的数。

:::info[Code 1]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,m,a[maxn],ans[105],q[105][105];
int dfs(int x){
	if(x>=n)return 0;
	if(~ans[x])return ans[x];
	int num=0;
	for(int i=0;i<=n-x;i++){
		int res=0;
		for(int j=0;j<=n-x;j++){
			if(i==j)continue;
			res=max(res,a[x+j+1]+dfs(x+j+1));
		}
		q[x][i]=res;
		if(res<q[x][num])num=i;
//		cerr<<x<<" "<<i<<" "<<q[x][i]<<"\n";
	}
	return ans[x]=q[x][num];
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	memset(ans,-1,sizeof(ans));
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	cout<<dfs(0)<<"\n";
	while(m--){
		memset(ans,-1,sizeof(ans));
		int x,y;
		cin>>x>>y;
		x++;
		a[x]=y;
		cout<<dfs(0)<<'\n';
	}
	return 0;
}

:::

我们可以发现，Aurora 一定会去除掉最有利于 Bianca 的数，然后 Bianca 选择第二有利于自己的选择。

其次，我们发现转移时只与我们当前的下标和枚举的位置有关。所以，我们将序列反转，当前的答案 $dp_i=dp_j+w_j$ 的次大值，其中 $j \in [1,i)$。

因此，对于这个遍历的过程，我们只需要维护当前 $dp_i+w_i$ 的最大值 $x$ 与最小值 $y$，然后每次让 $y$ 加上 $w_i$，根据情况决定是否需要交换 $x$ 和 $y$ 即可。

:::info[Code 2]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int n,m,a[maxn],mx1,mx2,res;
void dfs(int x){
	if(x>=n)return mx1=a[x],void();
	dfs(x+1);
	res=mx2;
	if(res+a[x]>mx1)mx2=mx1,mx1=res+a[x];
	else mx2=res+a[x];
}
void solve1(){
	dfs(0);
	cout<<res<<"\n";
	while(m--){
		int x,y;
		cin>>x>>y;
		x++;
		res=mx1=mx2=0;
		a[x]=y;
		dfs(0);
		cout<<res<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	solve1();
	return 0;
}

:::

考虑如何优化这个式子，我们发现，$w_i \le 50$ ，我们考虑维护最大值与次大值的差 $d$。转移时，若 $w_i \le d$，就让 $d=d-w_i$ ,否则 $d=w_i-d$。

然后我们将操作挂到线段树上，对于每一个节点维护一个 $f_i$ 表示进入当前区间时 $d=i$ 的情况下，离开这一段区间的 $d$。

:::info[Code 3]

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
struct s_tree{
	int a[maxn][51]={{0}};
	void update(int x,int l,int r,int p,int k){
		if(x==l&&x==r){
			for(int i=0;i<=50;i++)a[p][i]=abs(i-k);
			return ;
		}
		int mid=l+r>>1;
		if(x<=mid)update(x,l,mid,p<<1,k);
		else update(x,mid+1,r,p<<1|1,k);
		for(int i=0;i<=50;i++)a[p][i]=a[p<<1|1][a[p<<1][i]];
	}
	int query(){
		return a[1][0];
	}
}q;
int n,m,a[maxn],sum;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
	reverse(a+1,a+n+1);
	for(int i=1;i<=n;i++)q.update(i,1,n,1,a[i]);
	int tmp=q.query();
	cout<<(sum-tmp)/2<<"\n";
	while(m--){
		int x,y;
		cin>>x>>y;
		x=n-x;
		sum-=a[x];
		a[x]=y;
		sum+=a[x];
		q.update(x,1,n,1,a[x]);
		tmp=q.query();
		cout<<(sum-tmp)/2<<"\n";
	}
	return 0;
}

:::