CF1406D Three Sequences 做题记录

给定一个序列 $a_1,a_2,\ldots ,a_n$，长度为 $n$ 的序列 $b,c$ 符合以下条件

1. $a_i=b_i+c_i$
2. $b$ 为不下降序列，$c$ 为不上升序列，即 $b_i\geq b_{i-1}, c_i\leq c_{i-1}$

有 $q$ 个操作，每次操作把 $[l,r]$ 的数增加 $x$。求每次操作后最小的 $\max(b_i,c_i)$

看到单调不降和单调不升，就不难想到作差分。

设 $ad_i=a_i-a_{i-1},bd_i=b_i-b_{i-1},cd_i=c_i-c_{i-1}$（$a_0=0,b_0=0,c_0=0$），显然对于所有 $2\le i\le n$，有 $bd_i\ge 0,cd_i\le 0$。那么问题就转化为：

给定一个长度为 $n$ 的序列 $ad$，构造两个长度为 $n$，对于所有 $2\le i\le n$ 都满足 $bd_i\ge 0,cd_i\le 0$ 且对于所有 $1\le i\le n$ 都满足 $bd_i+cd_i=ad_i$ 的序列 $bd,cd$，使得 $\max(\sum bd_i,-\sum cd_i)$ 最小。

不难发现，因为 $bd_i\ge 0,cd_i\le 0$，所以对于所有 $ad_i\ge 0$ 的 $i$ 一定有 $bd_i=ad_i,cd_i=0$，对于所有 $ad_i<0$ 的 $i$ 一定有 $bd_i=0,cd_i=ad_i$。那么不妨钦定 $\max(\sum bd_i,cd_1)$ 一定为 $cd_1$，那么设 $sm=\sum\limits_{i=2}^n \max(ad_i,0)$，显然有 $ad_1-cd_1+sm\le cd_1$，那么有 $cd_1\ge \lceil\frac{ad_1+sm}{2}\rceil$，所以答案就是 $\lceil\frac{ad_1+sm}{2}\rceil$。

每次操作只会改动两个位置，那么动态维护差分即可。

代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005;

int n;
long long a[S];

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	for(int i=n;i>=1;i--) a[i]-=a[i-1];
	long long sm=0;
	for(int i=2;i<=n;i++) if(a[i]>0) sm+=a[i];
	printf("%lld\n",(sm+a[1])/2+(sm+a[1]>0)*((sm+a[1])%2));
	int q;
	scanf("%d",&q);
	while(q--)
	{
		int l,r;
		long long x;
		scanf("%d%d%lld",&l,&r,&x);
		r++;
		if(l>1)
		{
			if(a[l]>0) sm-=a[l];
			a[l]+=x;
			if(a[l]>0) sm+=a[l];
		}
		else a[l]+=x;
		if(r<=n)
		{
			if(a[r]>0) sm-=a[r];
			a[r]-=x;
			if(a[r]>0) sm+=a[r];
		}
		printf("%lld\n",(sm+a[1])/2+(sm+a[1]>0)*((sm+a[1])%2));
	} 
	return 0;
}